oj.uz

Submission #76723

# Submission time Handle Problem Language Result Execution time Memory
76723 2018-09-16T12:31:31 Z Mamnoon_Siam Highway Tolls (IOI18_highway) C++17
90 / 100
 453 ms 36380 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout << #s << " = " << s << endl

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 500005;

namespace {

vector<int> L, R, g[maxn], t[maxn], vis, lvl, pe, wot, where;
ll pathLen, A, B;
int S, T, tym = 0, n, m;

}

void bfs(int root) {
	queue<int> Q;
	Q.emplace(root);
	lvl[root] = 0;
	pe[root] = -1, vis[root] = 1;

	while(Q.size()) {
		int u = Q.front();
		Q.pop();
		for(int i : g[u]) {
			int v = L[i] ^ R[i] ^ u;
			if(!vis[v]) {
				vis[v] = 1;
				Q.emplace(v);
				lvl[v] = lvl[u] + 1;
				pe[v] = i;

				t[u].emplace_back(i);
				t[v].emplace_back(i);
			}
		}
	}
}

void dfs(int u) {
	vis[u] = 1;
	wot[tym] = u;
	where[u] = tym++;
	for(int i : t[u]) {
		int v = L[i] ^ R[i] ^ u;
		if(!vis[v]) {
			pe[v] = i;
			dfs(v);
		}
	}
}

void find_pair(int _N, std::vector<int> _U, std::vector<int> _V, int _A, int _B) {
	n = _N, L = _U, R = _V, A = _A, B = _B, m = _U.size();
	vis.assign(n, 0), lvl.assign(n, 0), pe.assign(n, 0), wot.assign(n, 0), where.assign(n, 0);

	for(int i = 0; i < m; i++) {
		g[L[i]].emplace_back(i);
		g[R[i]].emplace_back(i);
		// cout << i << " ----> " << L[i] << ' ' << R[i] << endl;
	}

	{
		vector<int> w(m);
		pathLen = ask(w) / A;
		// debug(pathLen);
	}

	int root;
	{
		int lo = 0, hi = m - 1, mid, ret = -1;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m);
			for(int i = 0; i <= mid; i++) {
				w[i] = 1;
			}
			if(ask(w) != A * pathLen) {
				ret = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		root = ret == -1 ? -1 : L[ret];
	}

	// debug(root);

	bfs(root);
	fill(vis.begin(), vis.end(), 0);
	pe[root] = -1;
	dfs(root);
	// for(int b : wot) cout << b << ' '; cout << endl;
	// for(int b : pe) cout << b << ' '; cout << endl;

	S = T = -1;

	{
		int lo = 0, hi = n - 1, mid;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m, 1);
			for(int i = 0; i <= mid; i++) {
				w[pe[wot[i]]] = 0;
			}
			if(ask(w) == A * pathLen) {
				S = wot[mid];
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
	}

	tym = 0;
	pe[S] = -1;
	fill(vis.begin(), vis.end(), 0);
	dfs(S);

	{
		int lo = 0, hi = n - 1, mid;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m, 1);
			for(int i = 0; i <= mid; i++) {
				w[pe[wot[i]]] = 0;
			}
			// int u = S;
			// while(pe[u] != -1) {
			// 	w[pe[u]] = 1;
			// 	u = u ^ L[pe[u]] ^ R[pe[u]];
			// }
			// for(int i = 0; i < m; i++) cout << i << ' '; cout << endl;
			// for(int b : w) cout << b << ' '; cout << endl;

			// debug(ask(w));

			if(ask(w) == A * pathLen) {
				T = wot[mid];
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
	}
	// debug(S), debug(T);
	answer(S, T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:77:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
highway.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
highway.cpp:128:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23784 KB Output is correct
2 Correct 21 ms 23720 KB Output is correct
3 Correct 24 ms 23812 KB Output is correct
4 Correct 26 ms 23720 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 25 ms 23720 KB Output is correct
8 Correct 24 ms 23804 KB Output is correct
9 Correct 25 ms 23716 KB Output is correct
10 Correct 22 ms 23908 KB Output is correct
11 Correct 25 ms 23720 KB Output is correct
12 Correct 25 ms 23804 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23972 KB Output is correct
2 Correct 50 ms 24924 KB Output is correct
3 Correct 439 ms 33984 KB Output is correct
4 Correct 323 ms 33932 KB Output is correct
5 Correct 309 ms 33888 KB Output is correct
6 Correct 283 ms 33900 KB Output is correct
7 Correct 343 ms 33900 KB Output is correct
8 Correct 314 ms 33924 KB Output is correct
9 Correct 313 ms 33956 KB Output is correct
10 Correct 357 ms 33912 KB Output is correct
11 Correct 365 ms 34248 KB Output is correct
12 Correct 341 ms 34684 KB Output is correct
13 Correct 331 ms 34436 KB Output is correct
14 Correct 319 ms 34436 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25208 KB Output is correct
2 Correct 67 ms 26488 KB Output is correct
3 Correct 79 ms 27916 KB Output is correct
4 Correct 226 ms 35424 KB Output is correct
5 Correct 221 ms 35468 KB Output is correct
6 Correct 197 ms 36060 KB Output is correct
7 Correct 232 ms 36380 KB Output is correct
8 Correct 188 ms 35676 KB Output is correct
9 Correct 191 ms 35852 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 51 ms 24824 KB Output is correct
3 Correct 227 ms 31760 KB Output is correct
4 Correct 337 ms 33896 KB Output is correct
5 Correct 371 ms 33888 KB Output is correct
6 Correct 306 ms 33988 KB Output is correct
7 Correct 285 ms 33912 KB Output is correct
8 Correct 286 ms 33964 KB Output is correct
9 Correct 285 ms 33892 KB Output is correct
10 Correct 334 ms 34020 KB Output is correct
11 Correct 340 ms 34264 KB Output is correct
12 Correct 358 ms 34768 KB Output is correct
13 Correct 312 ms 34512 KB Output is correct
14 Correct 356 ms 34440 KB Output is correct
15 Correct 312 ms 33920 KB Output is correct
16 Correct 283 ms 34012 KB Output is correct
17 Correct 315 ms 34352 KB Output is correct
18 Correct 289 ms 34624 KB Output is correct
19 Correct 271 ms 34012 KB Output is correct
20 Correct 335 ms 34780 KB Output is correct
21 Correct 252 ms 34768 KB Output is correct
22 Correct 262 ms 34760 KB Output is correct
23 Correct 304 ms 34612 KB Output is correct
24 Correct 296 ms 34832 KB Output is correct
25 Correct 360 ms 36340 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 24956 KB Output is correct
2 Correct 55 ms 24988 KB Output is correct
3 Correct 345 ms 34204 KB Output is correct
4 Correct 354 ms 34516 KB Output is correct
5 Correct 453 ms 35192 KB Output is correct
6 Correct 431 ms 35216 KB Output is correct
7 Correct 399 ms 35200 KB Output is correct
8 Correct 404 ms 35152 KB Output is correct
9 Correct 276 ms 30868 KB Output is correct
10 Correct 274 ms 30824 KB Output is correct
11 Correct 302 ms 31944 KB Output is correct
12 Correct 329 ms 33648 KB Output is correct
13 Correct 384 ms 34428 KB Output is correct
14 Correct 442 ms 34936 KB Output is correct
15 Correct 422 ms 34936 KB Output is correct
16 Correct 333 ms 31708 KB Output is correct
17 Correct 277 ms 34992 KB Output is correct
18 Correct 304 ms 35024 KB Output is correct
19 Correct 272 ms 34980 KB Output is correct
20 Correct 306 ms 35112 KB Output is correct
21 Correct 414 ms 35224 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24952 KB Output is correct
2 Correct 45 ms 24956 KB Output is correct
3 Correct 353 ms 34256 KB Output is correct
4 Partially correct 351 ms 34352 KB Output is partially correct
5 Partially correct 391 ms 34516 KB Output is partially correct
6 Correct 367 ms 35140 KB Output is correct
7 Correct 389 ms 34240 KB Output is correct
8 Partially correct 386 ms 34436 KB Output is partially correct
9 Partially correct 328 ms 34520 KB Output is partially correct
10 Partially correct 408 ms 35156 KB Output is partially correct
11 Partially correct 411 ms 35140 KB Output is partially correct
12 Correct 383 ms 35152 KB Output is correct
13 Correct 340 ms 31848 KB Output is correct
14 Correct 256 ms 30816 KB Output is correct
15 Correct 266 ms 31840 KB Output is correct
16 Correct 287 ms 30788 KB Output is correct
17 Correct 277 ms 31844 KB Output is correct
18 Correct 264 ms 30788 KB Output is correct
19 Correct 357 ms 33556 KB Output is correct
20 Partially correct 383 ms 34228 KB Output is partially correct
21 Partially correct 429 ms 34948 KB Output is partially correct
22 Partially correct 395 ms 34936 KB Output is partially correct
23 Partially correct 419 ms 34976 KB Output is partially correct
24 Partially correct 393 ms 34924 KB Output is partially correct
25 Partially correct 395 ms 34924 KB Output is partially correct
26 Partially correct 397 ms 34932 KB Output is partially correct
27 Correct 288 ms 34992 KB Output is correct
28 Correct 275 ms 34876 KB Output is correct
29 Correct 261 ms 35176 KB Output is correct
30 Partially correct 277 ms 35004 KB Output is partially correct
31 Correct 283 ms 35000 KB Output is correct
32 Partially correct 285 ms 34940 KB Output is partially correct
33 Partially correct 292 ms 35144 KB Output is partially correct
34 Partially correct 287 ms 34924 KB Output is partially correct
35 Correct 247 ms 34900 KB Output is correct
36 Partially correct 287 ms 34808 KB Output is partially correct
37 Partially correct 277 ms 35208 KB Output is partially correct
38 Correct 306 ms 34964 KB Output is correct
39 Correct 415 ms 35380 KB Output is correct
40 Correct 421 ms 35464 KB Output is correct
41 Partially correct 438 ms 35212 KB Output is partially correct
42 Partially correct 409 ms 35132 KB Output is partially correct