oj.uz

Submission #342916

# Submission time Handle Problem Language Result Execution time Memory
342916 2021-01-03T08:14:54 Z cki86201 Highway Tolls (IOI18_highway) C++11
100 / 100
 456 ms 11664 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

vector <int> EV;
vector <pii> E[100010];
int dv[2][100010], chk[100010];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = szz(U);
	rep(i, M) E[U[i]].pb({V[i], i}), E[V[i]].pb({U[i], i});
	EV.resize(M);
	ll dist = ask(EV);
	int low = 0, high = M - 1;
	while(low < high) {
		int mid = (low + high) >> 1;
		for(int i=low;i<=mid;i++) EV[i] = 1;
		if(ask(EV) != dist) {
			for(int i=low;i<=high;i++) EV[i] = 0;
			high = mid;
		}
		else low = mid + 1;
	}
	int P = U[low], Q = V[low], tl = low;
	rep(u, 2) {
		int st = (u ? Q : P);
		vector <int> q; q.pb(st);
		rep(i, N) dv[u][i] = -1;
		dv[u][st] = 0;
		rep(i, szz(q)) {
			int t = q[i];
			for(auto [e, _] : E[t]) if(dv[u][e] == -1) {
				dv[u][e] = dv[u][t] + 1;
				q.pb(e);
			}
		}
	}
	auto Find = [&](int P, vector <int> &C, int dis[]) {
		sort(all(C), [&](int x, int y) { return dis[x] < dis[y]; });
		int low = 0, high = szz(C) - 1;
		while(low < high) {
			int mid = (low + high) >> 1;
			rep(i, M) EV[i] = (i != tl && chk[U[i]] != chk[V[i]]);
			for(int i=mid+1;i<szz(C);i++) {
				int x = C[i];
				for(auto [e, id] : E[x]) {
					if(dis[e] + 1 == dis[x]) EV[id] = 1;
				}
			}
			if(ask(EV) != dist) low = mid + 1;
			else high = mid;
		}
		return C[low];
	};
	vector <int> R[2];
	rep(i, N) {
		if(dv[0][i] < dv[1][i]) R[0].pb(i), chk[i] = 0;
		else if(dv[0][i] > dv[1][i]) R[1].pb(i), chk[i] = 1;
		else chk[i] = 2;
	}
	answer(Find(P, R[0], dv[0]), Find(Q, R[1], dv[1]));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |    for(auto [e, _] : E[t]) if(dv[u][e] == -1) {
      |             ^
highway.cpp: In lambda function:
highway.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [e, id] : E[x]) {
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2736 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 20 ms 3436 KB Output is correct
3 Correct 263 ms 9976 KB Output is correct
4 Correct 234 ms 9836 KB Output is correct
5 Correct 229 ms 9848 KB Output is correct
6 Correct 196 ms 9804 KB Output is correct
7 Correct 260 ms 9964 KB Output is correct
8 Correct 348 ms 9880 KB Output is correct
9 Correct 345 ms 10028 KB Output is correct
10 Correct 223 ms 10040 KB Output is correct
11 Correct 349 ms 9272 KB Output is correct
12 Correct 318 ms 9172 KB Output is correct
13 Correct 318 ms 9240 KB Output is correct
14 Correct 318 ms 9312 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3436 KB Output is correct
2 Correct 31 ms 4136 KB Output is correct
3 Correct 47 ms 4804 KB Output is correct
4 Correct 140 ms 9012 KB Output is correct
5 Correct 140 ms 9000 KB Output is correct
6 Correct 134 ms 9264 KB Output is correct
7 Correct 139 ms 9348 KB Output is correct
8 Correct 120 ms 8992 KB Output is correct
9 Correct 136 ms 9176 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 20 ms 3436 KB Output is correct
3 Correct 242 ms 8364 KB Output is correct
4 Correct 310 ms 9884 KB Output is correct
5 Correct 328 ms 9808 KB Output is correct
6 Correct 317 ms 9820 KB Output is correct
7 Correct 321 ms 9908 KB Output is correct
8 Correct 298 ms 9956 KB Output is correct
9 Correct 270 ms 9776 KB Output is correct
10 Correct 270 ms 9868 KB Output is correct
11 Correct 308 ms 9364 KB Output is correct
12 Correct 252 ms 9288 KB Output is correct
13 Correct 323 ms 9240 KB Output is correct
14 Correct 331 ms 9168 KB Output is correct
15 Correct 337 ms 9896 KB Output is correct
16 Correct 343 ms 9980 KB Output is correct
17 Correct 268 ms 9228 KB Output is correct
18 Correct 318 ms 9236 KB Output is correct
19 Correct 335 ms 9868 KB Output is correct
20 Correct 352 ms 9232 KB Output is correct
21 Correct 165 ms 9960 KB Output is correct
22 Correct 207 ms 9952 KB Output is correct
23 Correct 207 ms 9712 KB Output is correct
24 Correct 250 ms 9880 KB Output is correct
25 Correct 196 ms 9384 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3564 KB Output is correct
2 Correct 24 ms 3692 KB Output is correct
3 Correct 223 ms 10216 KB Output is correct
4 Correct 308 ms 10312 KB Output is correct
5 Correct 385 ms 11552 KB Output is correct
6 Correct 386 ms 11284 KB Output is correct
7 Correct 369 ms 11340 KB Output is correct
8 Correct 342 ms 11184 KB Output is correct
9 Correct 187 ms 8872 KB Output is correct
10 Correct 200 ms 9300 KB Output is correct
11 Correct 207 ms 9632 KB Output is correct
12 Correct 308 ms 10680 KB Output is correct
13 Correct 361 ms 11100 KB Output is correct
14 Correct 367 ms 11352 KB Output is correct
15 Correct 392 ms 11292 KB Output is correct
16 Correct 244 ms 9720 KB Output is correct
17 Correct 204 ms 10032 KB Output is correct
18 Correct 230 ms 10424 KB Output is correct
19 Correct 225 ms 10300 KB Output is correct
20 Correct 233 ms 10344 KB Output is correct
21 Correct 444 ms 11592 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3692 KB Output is correct
2 Correct 19 ms 3564 KB Output is correct
3 Correct 320 ms 9984 KB Output is correct
4 Correct 345 ms 10100 KB Output is correct
5 Correct 345 ms 10348 KB Output is correct
6 Correct 332 ms 11264 KB Output is correct
7 Correct 328 ms 10392 KB Output is correct
8 Correct 346 ms 10320 KB Output is correct
9 Correct 334 ms 10384 KB Output is correct
10 Correct 387 ms 11272 KB Output is correct
11 Correct 379 ms 11284 KB Output is correct
12 Correct 369 ms 11164 KB Output is correct
13 Correct 209 ms 9616 KB Output is correct
14 Correct 202 ms 9304 KB Output is correct
15 Correct 214 ms 9692 KB Output is correct
16 Correct 182 ms 9436 KB Output is correct
17 Correct 221 ms 9840 KB Output is correct
18 Correct 188 ms 9292 KB Output is correct
19 Correct 337 ms 10692 KB Output is correct
20 Correct 383 ms 11108 KB Output is correct
21 Correct 410 ms 11252 KB Output is correct
22 Correct 399 ms 11280 KB Output is correct
23 Correct 409 ms 11440 KB Output is correct
24 Correct 376 ms 11228 KB Output is correct
25 Correct 397 ms 11268 KB Output is correct
26 Correct 402 ms 11212 KB Output is correct
27 Correct 207 ms 10160 KB Output is correct
28 Correct 195 ms 10164 KB Output is correct
29 Correct 173 ms 10324 KB Output is correct
30 Correct 157 ms 10232 KB Output is correct
31 Correct 182 ms 10304 KB Output is correct
32 Correct 226 ms 10032 KB Output is correct
33 Correct 206 ms 10320 KB Output is correct
34 Correct 227 ms 10108 KB Output is correct
35 Correct 187 ms 10100 KB Output is correct
36 Correct 231 ms 10004 KB Output is correct
37 Correct 228 ms 10260 KB Output is correct
38 Correct 207 ms 10332 KB Output is correct
39 Correct 447 ms 11664 KB Output is correct
40 Correct 453 ms 11652 KB Output is correct
41 Correct 257 ms 11660 KB Output is correct
42 Correct 456 ms 11420 KB Output is correct