oj.uz

Submission #76722

# Submission time Handle Problem Language Result Execution time Memory
76722 2018-09-16T12:26:32 Z Mamnoon_Siam Highway Tolls (IOI18_highway) C++17
90 / 100
 444 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 23800 KB Output is correct
2 Correct 24 ms 23812 KB Output is correct
3 Correct 25 ms 23720 KB Output is correct
4 Correct 23 ms 23720 KB Output is correct
5 Correct 24 ms 23848 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 23 ms 23720 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23840 KB Output is correct
10 Correct 29 ms 23804 KB Output is correct
11 Correct 24 ms 23804 KB Output is correct
12 Correct 24 ms 23800 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 49 ms 24824 KB Output is correct
3 Correct 311 ms 33912 KB Output is correct
4 Correct 351 ms 33888 KB Output is correct
5 Correct 359 ms 33896 KB Output is correct
6 Correct 308 ms 33912 KB Output is correct
7 Correct 336 ms 33896 KB Output is correct
8 Correct 316 ms 33912 KB Output is correct
9 Correct 305 ms 33916 KB Output is correct
10 Correct 337 ms 33908 KB Output is correct
11 Correct 326 ms 34252 KB Output is correct
12 Correct 332 ms 34676 KB Output is correct
13 Correct 370 ms 34456 KB Output is correct
14 Correct 305 ms 34452 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25120 KB Output is correct
2 Correct 53 ms 26512 KB Output is correct
3 Correct 95 ms 27916 KB Output is correct
4 Correct 204 ms 35460 KB Output is correct
5 Correct 178 ms 35476 KB Output is correct
6 Correct 219 ms 36064 KB Output is correct
7 Correct 206 ms 36380 KB Output is correct
8 Correct 197 ms 35676 KB Output is correct
9 Correct 184 ms 35952 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 47 ms 24920 KB Output is correct
3 Correct 221 ms 31688 KB Output is correct
4 Correct 341 ms 33912 KB Output is correct
5 Correct 282 ms 33904 KB Output is correct
6 Correct 305 ms 33892 KB Output is correct
7 Correct 280 ms 34036 KB Output is correct
8 Correct 287 ms 33888 KB Output is correct
9 Correct 320 ms 33904 KB Output is correct
10 Correct 310 ms 33900 KB Output is correct
11 Correct 330 ms 34276 KB Output is correct
12 Correct 372 ms 34776 KB Output is correct
13 Correct 361 ms 34504 KB Output is correct
14 Correct 329 ms 34448 KB Output is correct
15 Correct 300 ms 33904 KB Output is correct
16 Correct 273 ms 34012 KB Output is correct
17 Correct 364 ms 34456 KB Output is correct
18 Correct 322 ms 34624 KB Output is correct
19 Correct 282 ms 33932 KB Output is correct
20 Correct 276 ms 34784 KB Output is correct
21 Correct 200 ms 34820 KB Output is correct
22 Correct 288 ms 34776 KB Output is correct
23 Correct 292 ms 34620 KB Output is correct
24 Correct 307 ms 34808 KB Output is correct
25 Correct 357 ms 36332 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 24944 KB Output is correct
2 Correct 58 ms 24904 KB Output is correct
3 Correct 390 ms 34220 KB Output is correct
4 Correct 380 ms 34508 KB Output is correct
5 Correct 444 ms 35212 KB Output is correct
6 Correct 416 ms 35232 KB Output is correct
7 Correct 397 ms 35144 KB Output is correct
8 Correct 400 ms 35152 KB Output is correct
9 Correct 315 ms 30868 KB Output is correct
10 Correct 265 ms 30832 KB Output is correct
11 Correct 293 ms 31852 KB Output is correct
12 Correct 357 ms 33644 KB Output is correct
13 Correct 361 ms 34416 KB Output is correct
14 Correct 431 ms 34920 KB Output is correct
15 Correct 427 ms 34948 KB Output is correct
16 Correct 296 ms 31720 KB Output is correct
17 Correct 285 ms 34912 KB Output is correct
18 Correct 268 ms 34996 KB Output is correct
19 Correct 295 ms 34932 KB Output is correct
20 Correct 314 ms 35040 KB Output is correct
21 Correct 394 ms 35236 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24824 KB Output is correct
2 Correct 56 ms 24952 KB Output is correct
3 Correct 382 ms 34304 KB Output is correct
4 Partially correct 366 ms 34356 KB Output is partially correct
5 Partially correct 404 ms 34524 KB Output is partially correct
6 Correct 375 ms 35276 KB Output is correct
7 Correct 356 ms 34248 KB Output is correct
8 Partially correct 346 ms 34356 KB Output is partially correct
9 Partially correct 366 ms 34504 KB Output is partially correct
10 Partially correct 425 ms 35136 KB Output is partially correct
11 Partially correct 389 ms 35140 KB Output is partially correct
12 Correct 398 ms 35184 KB Output is correct
13 Correct 335 ms 31856 KB Output is correct
14 Correct 266 ms 30788 KB Output is correct
15 Correct 284 ms 31852 KB Output is correct
16 Correct 275 ms 30808 KB Output is correct
17 Correct 301 ms 31880 KB Output is correct
18 Correct 274 ms 30776 KB Output is correct
19 Correct 359 ms 33520 KB Output is correct
20 Partially correct 374 ms 34224 KB Output is partially correct
21 Partially correct 395 ms 34932 KB Output is partially correct
22 Partially correct 425 ms 34896 KB Output is partially correct
23 Partially correct 421 ms 34952 KB Output is partially correct
24 Partially correct 437 ms 34924 KB Output is partially correct
25 Partially correct 384 ms 34928 KB Output is partially correct
26 Partially correct 374 ms 35048 KB Output is partially correct
27 Correct 288 ms 34976 KB Output is correct
28 Correct 276 ms 34944 KB Output is correct
29 Correct 263 ms 35176 KB Output is correct
30 Partially correct 290 ms 34956 KB Output is partially correct
31 Correct 275 ms 35116 KB Output is correct
32 Partially correct 279 ms 34828 KB Output is partially correct
33 Partially correct 328 ms 35252 KB Output is partially correct
34 Partially correct 262 ms 34992 KB Output is partially correct
35 Correct 272 ms 34892 KB Output is correct
36 Partially correct 315 ms 34792 KB Output is partially correct
37 Partially correct 275 ms 35216 KB Output is partially correct
38 Correct 323 ms 34948 KB Output is correct
39 Correct 406 ms 35468 KB Output is correct
40 Correct 409 ms 35432 KB Output is correct
41 Partially correct 429 ms 35152 KB Output is partially correct
42 Partially correct 403 ms 35124 KB Output is partially correct