CSES - KILO 2018 4/5

CSES - KILO 2018 4/5 - Results

Submission details
Task:	Ping
Sender:	ArktinenKarpalo
Submission time:	2018-09-27 17:55:07 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.03 s	details
#2	ACCEPTED	0.02 s	details
#3	ACCEPTED	0.74 s	details
#4	ACCEPTED	0.20 s	details
#5	ACCEPTED	0.29 s	details
#6	ACCEPTED	0.67 s	details
#7	ACCEPTED	0.68 s	details
#8	ACCEPTED	0.25 s	details
#9	ACCEPTED	0.48 s	details
#10	ACCEPTED	0.30 s	details
#11	ACCEPTED	0.12 s	details
#12	ACCEPTED	0.14 s	details
#13	ACCEPTED	0.12 s	details
#14	ACCEPTED	0.12 s	details
#15	ACCEPTED	0.54 s	details
#16	ACCEPTED	0.47 s	details
#17	ACCEPTED	0.14 s	details

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define M 100000007
#define N (1<<17)
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, q, p, f, ff, fff;
pair<pair<int,int>, int> v[101010];
multiset<pair<int,int>> st[101010]; // 1 = mihin, 2 = cost

ll dist[101010];
int z[101010];
ll dijkstra() {
	for(int i=1; i<=n; i++) {
		z[i] = 0;
		dist[i] = 1e9+1;
	}
	dist[1] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(0, 1));
	while(!pq.empty()) {
		int s = pq.top().second;
		ll cst = -pq.top().first;
		pq.pop();
		if(z[s])
			continue;
		z[s] = 1;
		for(auto u:st[s]) {
			if(cst+u.second < dist[u.first]) {
				dist[u.first] = cst+u.second;
				pq.push(make_pair(-dist[u.first], u.first));
			}
		}
	}
	return dist[n];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> q >> p;
	for(int i=0; i<q; i++) {
		cin >> f >> ff >> fff;
		v[i] = make_pair(make_pair(f, ff), fff);	
	}
	int a = 0;
	int b = q-1;
	int nyton = -1;
	int cnt = 0;
	while(a<=b) {
		cnt++;
		int c = (a+b)/2;
		while(nyton<c) {
			nyton++;
			int mista = v[nyton].first.first;
			int mihin = v[nyton].first.second;
			int maksaa = v[nyton].second;
			st[mista].insert(make_pair(mihin, maksaa));
			st[mihin].insert(make_pair(mista, maksaa));
		}
		while(nyton>c) {
			int mista = v[nyton].first.first;
			int mihin = v[nyton].first.second;
			int maksaa = v[nyton].second;
			st[mista].erase(st[mista].find(make_pair(mihin, maksaa)));
			st[mihin].erase(st[mihin].find(make_pair(mista, maksaa)));
			nyton--;
		}
		if(dijkstra()<=p)
			b = c-1;
		else
			a = c+1;
	}
		while(nyton<a+1) {
			nyton++;
			int mista = v[nyton].first.first;
			int mihin = v[nyton].first.second;
			int maksaa = v[nyton].second;
			st[mista].insert(make_pair(mihin, maksaa));
			st[mihin].insert(make_pair(mista, maksaa));
		}
		while(nyton>a+1) {
			int mista = v[nyton].first.first;
			int mihin = v[nyton].first.second;
			int maksaa = v[nyton].second;
			st[mista].erase(st[mista].find(make_pair(mihin, maksaa)));
			st[mihin].erase(st[mihin].find(make_pair(mista, maksaa)));
			nyton--;
		}
	if(dijkstra()<=p)
		cout << a+1;
	else
		cout << "QAQ";
}

Test details

Test 1

Verdict: ACCEPTED

input
`4 5 4 1 4 5 2 1 1 4 3 2 1 3 2 ...` view save

correct output
`4` view save

user output
`4` view save

Test 2

Verdict: ACCEPTED

input
`4 3 4 1 3 2 3 4 3 2 4 1` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 3

Verdict: ACCEPTED

input
`79228 100000 609719088 71059 11143 686695 68230 2527 877907 53438 29888 202308 3549 78720 356072 ...` view save

correct output
`95914` view save

user output
`95914` view save

Test 4

Verdict: ACCEPTED

input
`54105 100000 146069808 21034 33530 208067 31369 39373 438341 53601 30432 458004 44664 29661 964679 ...` view save

correct output
`47249` view save

user output
`47249` view save

Test 5

Verdict: ACCEPTED

input
`27534 100000 630452185 4554 20869 156656 18125 16857 129766 7327 23355 162783 12208 19586 330973 ...` view save

correct output
`37629` view save

user output
`37629` view save

Test 6

Verdict: ACCEPTED

input
`100000 100000 1896201 37633 24342 686408 21326 35599 18816 68870 92002 748527 87772 68354 816268 ...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 7

Verdict: ACCEPTED

input
`100000 100000 2753856 28301 86840 226813 23531 88963 140812 81527 28867 31169 81346 50536 187421 ...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 8

Verdict: ACCEPTED

input
`100000 100000 8894369 96437 89061 279201 93127 41538 16340 5646 70264 970395 96240 15676 526054 ...` view save

correct output
`89568` view save

user output
`89568` view save

Test 9

Verdict: ACCEPTED

input
`100000 100000 8920310 51576 49748 441411 75379 58501 720057 77269 34775 380776 45446 74022 804975 ...` view save

correct output
`94792` view save

user output
`94792` view save

Test 10

Verdict: ACCEPTED

input
`5000 100000 699655 4460 4283 850197 3421 2128 903580 3335 401 848289 4975 4482 241023 ...` view save

correct output
`58358` view save

user output
`58358` view save

Test 11

Verdict: ACCEPTED

input
`5000 100000 2906768 4100 2619 553305 4947 1462 263251 1703 4236 286383 4228 4797 635722 ...` view save

correct output
`12392` view save

user output
`12392` view save

Test 12

Verdict: ACCEPTED

input
`5000 100000 8525016 4452 4625 772169 4941 929 373626 2610 379 935441 3007 4 402654 ...` view save

correct output
`16113` view save

user output
`16113` view save

Test 13

Verdict: ACCEPTED

input
`5000 100000 6672172 2548 393 274388 1269 4076 230068 24 3024 596999 4658 2589 401693 ...` view save

correct output
`3674` view save

user output
`3674` view save

Test 14

Verdict: ACCEPTED

input
`100000 100000 1000000000 61435 73156 809653003 31805 69457 997174565 46138 4746 664487503 77749 57316 726729812 ...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 15

Verdict: ACCEPTED

input
`70000 100000 389981 69496 42899 329 42449 25317 445 2446 37175 175 4791 27488 51 ...` view save

correct output
`71694` view save

user output
`71694` view save

Test 16

Verdict: ACCEPTED

input
`70000 100000 7413515 66481 13331 14 34935 8021 953 66946 55602 904 49080 1580 157 ...` view save

correct output
`82046` view save

user output
`82046` view save

Test 17

Verdict: ACCEPTED

input
`20000 100000 100000000 1 2 10000 2 3 10000 3 4 10000 4 5 10000 ...` view save

correct output
`50001` view save

user output
`50001` view save

KILO 2018 4/5

Ping

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Tasks

Submissions (ArktinenKarpalo)