oj.uz

Submission #102732

# Submission time Handle Problem Language Result Execution time Memory
102732 2019-03-27T09:48:01 Z bert30702 Highway Tolls (IOI18_highway) C++17
100 / 100
 408 ms 63832 KB 
#include <bits/stdc++.h>
#include "highway.h"
#define pii pair<int, int>
#define F first
#define S second
#define int long long
using namespace std;
const int MX = 1e6 + 100;
vector<pii> G1[MX], G2[MX];
bitset<MX> pass, edge;
int deep[MX];
vector<pii> que;
void dfs(int u, int l, int d) {
	que.push_back({u, l});
	deep[u] = d;
	for(auto it: G2[u]) dfs(it.F, it.S, d + 1);
}
void find_pair(int32_t n, vector<int32_t> u, vector<int32_t> v, int32_t a, int32_t b) {
	for(int i = 0; i < u.size(); i ++) {
		G1[u[i]].push_back({v[i], i});
		G1[v[i]].push_back({u[i], i});
	}
	int d = ask(vector<int32_t>(u.size(), 0));
	int l = 0, r = u.size() - 1;
	while(l != r) {
		int m = l + r >> 1;
		vector<int32_t> query(u.size(), 0);
		for(int i = 0; i <= m; i ++) query[i] = 1;
		if(ask(query) > d) r = m;
		else               l = m + 1;
	}
	pass[u[l]] = pass[v[l]] = edge[l] = true;
	queue<int> q;
	q.push(u[l]); q.push(v[l]);
	while(q.size()) {
		int p = q.front(); q.pop();
		for(auto i: G1[p]) {
			if(!pass[i.F]) {
				edge[i.S] = pass[i.F] = true;
				G2[p].push_back(i);
				q.push(i.F);
			}
		}
	}
	vector<int> Yeeee = {u[l], v[l]}, YEEEE;
	for(auto it: Yeeee) {
		que.clear();
		dfs(it, l, 1);
		sort(que.begin(), que.end(), [](pii a, pii b) {
			return deep[a.F] < deep[b.F];	
		});
		int l = 0, r = que.size() - 1;
		while(l != r) {
			int m = l + r >> 1;
			vector<int32_t> query(u.size(), 1);
			for(int i = 0; i < u.size(); i ++) {
				if(edge[i]) query[i] = 0;
			}
			for(int i = m + 1; i <= r; i ++) {
				query[que[i].S] = 1;
			}
			if(ask(query) > d) l = m + 1;
			else               r = m;
		}
		YEEEE.push_back(que[l].F);
	}
	answer(YEEEE[0], YEEEE[1]);
}

Compilation message

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i ++) {
                 ~~^~~~~~~~~~
highway.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
highway.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 48 ms 47296 KB Output is correct
3 Correct 43 ms 47300 KB Output is correct
4 Correct 45 ms 47272 KB Output is correct
5 Correct 44 ms 47224 KB Output is correct
6 Correct 53 ms 47284 KB Output is correct
7 Correct 44 ms 47352 KB Output is correct
8 Correct 44 ms 47284 KB Output is correct
9 Correct 44 ms 47224 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 45 ms 47380 KB Output is correct
12 Correct 45 ms 47224 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 66 ms 48632 KB Output is correct
3 Correct 257 ms 58948 KB Output is correct
4 Correct 232 ms 58880 KB Output is correct
5 Correct 255 ms 58972 KB Output is correct
6 Correct 237 ms 58952 KB Output is correct
7 Correct 252 ms 58940 KB Output is correct
8 Correct 268 ms 58928 KB Output is correct
9 Correct 286 ms 58952 KB Output is correct
10 Correct 250 ms 58864 KB Output is correct
11 Correct 278 ms 59320 KB Output is correct
12 Correct 292 ms 60920 KB Output is correct
13 Correct 309 ms 60644 KB Output is correct
14 Correct 308 ms 60664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 49192 KB Output is correct
2 Correct 76 ms 50676 KB Output is correct
3 Correct 99 ms 52556 KB Output is correct
4 Correct 218 ms 61388 KB Output is correct
5 Correct 212 ms 61400 KB Output is correct
6 Correct 218 ms 63132 KB Output is correct
7 Correct 234 ms 63832 KB Output is correct
8 Correct 234 ms 62016 KB Output is correct
9 Correct 221 ms 63004 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 67 ms 48424 KB Output is correct
3 Correct 220 ms 56524 KB Output is correct
4 Correct 252 ms 58896 KB Output is correct
5 Correct 268 ms 58944 KB Output is correct
6 Correct 282 ms 58952 KB Output is correct
7 Correct 258 ms 58940 KB Output is correct
8 Correct 308 ms 58840 KB Output is correct
9 Correct 266 ms 58944 KB Output is correct
10 Correct 253 ms 59072 KB Output is correct
11 Correct 281 ms 60408 KB Output is correct
12 Correct 320 ms 60700 KB Output is correct
13 Correct 286 ms 60804 KB Output is correct
14 Correct 298 ms 59736 KB Output is correct
15 Correct 264 ms 58856 KB Output is correct
16 Correct 252 ms 58916 KB Output is correct
17 Correct 276 ms 60548 KB Output is correct
18 Correct 290 ms 60924 KB Output is correct
19 Correct 259 ms 58972 KB Output is correct
20 Correct 273 ms 60972 KB Output is correct
21 Correct 220 ms 58812 KB Output is correct
22 Correct 231 ms 58796 KB Output is correct
23 Correct 233 ms 57024 KB Output is correct
24 Correct 222 ms 57468 KB Output is correct
25 Correct 251 ms 63248 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 48612 KB Output is correct
2 Correct 68 ms 48784 KB Output is correct
3 Correct 307 ms 59684 KB Output is correct
4 Correct 317 ms 60248 KB Output is correct
5 Correct 383 ms 61372 KB Output is correct
6 Correct 374 ms 60352 KB Output is correct
7 Correct 378 ms 60332 KB Output is correct
8 Correct 381 ms 60328 KB Output is correct
9 Correct 310 ms 56356 KB Output is correct
10 Correct 306 ms 57332 KB Output is correct
11 Correct 299 ms 58196 KB Output is correct
12 Correct 399 ms 59604 KB Output is correct
13 Correct 393 ms 59892 KB Output is correct
14 Correct 349 ms 60328 KB Output is correct
15 Correct 381 ms 61476 KB Output is correct
16 Correct 333 ms 57936 KB Output is correct
17 Correct 240 ms 58588 KB Output is correct
18 Correct 213 ms 59132 KB Output is correct
19 Correct 228 ms 58632 KB Output is correct
20 Correct 236 ms 58740 KB Output is correct
21 Correct 408 ms 61328 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 48584 KB Output is correct
2 Correct 73 ms 48780 KB Output is correct
3 Correct 307 ms 58680 KB Output is correct
4 Correct 311 ms 58756 KB Output is correct
5 Correct 314 ms 59108 KB Output is correct
6 Correct 373 ms 60320 KB Output is correct
7 Correct 294 ms 59564 KB Output is correct
8 Correct 310 ms 59392 KB Output is correct
9 Correct 325 ms 59116 KB Output is correct
10 Correct 395 ms 60288 KB Output is correct
11 Correct 391 ms 60360 KB Output is correct
12 Correct 396 ms 60320 KB Output is correct
13 Correct 325 ms 58212 KB Output is correct
14 Correct 294 ms 57344 KB Output is correct
15 Correct 323 ms 58196 KB Output is correct
16 Correct 275 ms 57360 KB Output is correct
17 Correct 323 ms 58196 KB Output is correct
18 Correct 300 ms 57324 KB Output is correct
19 Correct 396 ms 59524 KB Output is correct
20 Correct 389 ms 61072 KB Output is correct
21 Correct 388 ms 60452 KB Output is correct
22 Correct 399 ms 60456 KB Output is correct
23 Correct 384 ms 60452 KB Output is correct
24 Correct 405 ms 60340 KB Output is correct
25 Correct 390 ms 61460 KB Output is correct
26 Correct 383 ms 61480 KB Output is correct
27 Correct 262 ms 58820 KB Output is correct
28 Correct 254 ms 58548 KB Output is correct
29 Correct 226 ms 59420 KB Output is correct
30 Correct 247 ms 58772 KB Output is correct
31 Correct 229 ms 58736 KB Output is correct
32 Correct 248 ms 58576 KB Output is correct
33 Correct 222 ms 59240 KB Output is correct
34 Correct 247 ms 58772 KB Output is correct
35 Correct 252 ms 58684 KB Output is correct
36 Correct 242 ms 58528 KB Output is correct
37 Correct 257 ms 59164 KB Output is correct
38 Correct 243 ms 58856 KB Output is correct
39 Correct 396 ms 61988 KB Output is correct
40 Correct 383 ms 62224 KB Output is correct
41 Correct 369 ms 61736 KB Output is correct
42 Correct 392 ms 60544 KB Output is correct