oj.uz

Submission #415746

# Submission time Handle Problem Language Result Execution time Memory
415746 2021-06-01T12:49:34 Z _fractal Highway Tolls (IOI18_highway) C++14
100 / 100
 616 ms 11776 KB 
#include "highway.h"
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<pair<int, int>>> g;
long long cur;
int M;

int calc(int v, vector<int> t) {
	int tl = 0, tr = t.size() - 1, ans = v;
	vector<int> get(M, 0);
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (auto &i : get) i = 0;
		for (int i = tm + 1; i < t.size(); ++i) {
			for (auto to : g[t[i]])
				get[to.second] = 1;	
		}
		if (ask(get) == cur) {
			ans = t[tm];
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}	
	return ans;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	vector<int> activ;
	vector<int> get(M, 0);
	vector<int> was(N, 0);
	g = vector<vector<pair<int, int>>> (N, vector<pair<int, int>>(0));
	cur = ask(get);
	for (int i = 0; i < M; ++i) {
		g[V[i]].push_back({U[i], i});
		g[U[i]].push_back({V[i], i});
	}
	int tl = 0, tr = M, ans = -1;
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (int i = 0; i < M; ++i)
			get[i] = (i > tm);
		if (ask(get) == cur) {
			ans = tm;
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}
	queue<int> q;
	vector<int> d(N, -1), col(N, 0);
	vector<int> is[2];
	q.push(U[ans]), q.push(V[ans]);
	d[U[ans]] = d[V[ans]] = 0;
	col[U[ans]] = 0;
	col[V[ans]] = 1;
	while (q.size()) {
		int v = q.front();
		q.pop();
		is[col[v]].push_back(v);
		for (auto it : g[v]) {
			int to = it.first, c = it.second;
			if (d[to] == -1) {
				d[to] = d[v] + 1;
				col[to] = col[v];
				q.push(to);
			}
		}
	}
	int a = calc(U[ans], is[0]);
	int b = calc(V[ans], is[1]);
	answer(a, b);
	return;
}

Compilation message

highway.cpp: In function 'int calc(int, std::vector<int>)':
highway.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (int i = tm + 1; i < t.size(); ++i) {
      |                        ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:68:23: warning: unused variable 'c' [-Wunused-variable]
   68 |    int to = it.first, c = it.second;
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 2 ms 200 KB Output is correct
9 Correct 2 ms 200 KB Output is correct
10 Correct 3 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 2 ms 328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 22 ms 1356 KB Output is correct
3 Correct 350 ms 9828 KB Output is correct
4 Correct 258 ms 9716 KB Output is correct
5 Correct 291 ms 9704 KB Output is correct
6 Correct 176 ms 9920 KB Output is correct
7 Correct 300 ms 9748 KB Output is correct
8 Correct 437 ms 9700 KB Output is correct
9 Correct 265 ms 9804 KB Output is correct
10 Correct 178 ms 9836 KB Output is correct
11 Correct 408 ms 9172 KB Output is correct
12 Correct 294 ms 9088 KB Output is correct
13 Correct 394 ms 9264 KB Output is correct
14 Correct 284 ms 9228 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1256 KB Output is correct
2 Correct 24 ms 2232 KB Output is correct
3 Correct 69 ms 3348 KB Output is correct
4 Correct 223 ms 8964 KB Output is correct
5 Correct 184 ms 8988 KB Output is correct
6 Correct 205 ms 9200 KB Output is correct
7 Correct 194 ms 9240 KB Output is correct
8 Correct 180 ms 9076 KB Output is correct
9 Correct 112 ms 9156 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 18 ms 1256 KB Output is correct
3 Correct 175 ms 7632 KB Output is correct
4 Correct 311 ms 9824 KB Output is correct
5 Correct 433 ms 9824 KB Output is correct
6 Correct 306 ms 9820 KB Output is correct
7 Correct 230 ms 9844 KB Output is correct
8 Correct 403 ms 9832 KB Output is correct
9 Correct 285 ms 9688 KB Output is correct
10 Correct 246 ms 9908 KB Output is correct
11 Correct 306 ms 9104 KB Output is correct
12 Correct 152 ms 9180 KB Output is correct
13 Correct 406 ms 9200 KB Output is correct
14 Correct 269 ms 8996 KB Output is correct
15 Correct 401 ms 9816 KB Output is correct
16 Correct 306 ms 9708 KB Output is correct
17 Correct 358 ms 9132 KB Output is correct
18 Correct 328 ms 9152 KB Output is correct
19 Correct 405 ms 9936 KB Output is correct
20 Correct 340 ms 9108 KB Output is correct
21 Correct 141 ms 10348 KB Output is correct
22 Correct 216 ms 10340 KB Output is correct
23 Correct 227 ms 10028 KB Output is correct
24 Correct 165 ms 9924 KB Output is correct
25 Correct 173 ms 9324 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1388 KB Output is correct
2 Correct 31 ms 1440 KB Output is correct
3 Correct 456 ms 10128 KB Output is correct
4 Correct 471 ms 10616 KB Output is correct
5 Correct 377 ms 11620 KB Output is correct
6 Correct 457 ms 11776 KB Output is correct
7 Correct 412 ms 11732 KB Output is correct
8 Correct 573 ms 11724 KB Output is correct
9 Correct 270 ms 7788 KB Output is correct
10 Correct 269 ms 7988 KB Output is correct
11 Correct 287 ms 8880 KB Output is correct
12 Correct 283 ms 10620 KB Output is correct
13 Correct 282 ms 11168 KB Output is correct
14 Correct 517 ms 11716 KB Output is correct
15 Correct 446 ms 11676 KB Output is correct
16 Correct 334 ms 9088 KB Output is correct
17 Correct 239 ms 10360 KB Output is correct
18 Correct 175 ms 10396 KB Output is correct
19 Correct 192 ms 10516 KB Output is correct
20 Correct 229 ms 10432 KB Output is correct
21 Correct 405 ms 11704 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1380 KB Output is correct
2 Correct 17 ms 1444 KB Output is correct
3 Correct 311 ms 10292 KB Output is correct
4 Correct 321 ms 10288 KB Output is correct
5 Correct 391 ms 10620 KB Output is correct
6 Correct 402 ms 11696 KB Output is correct
7 Correct 369 ms 10280 KB Output is correct
8 Correct 332 ms 10388 KB Output is correct
9 Correct 449 ms 10620 KB Output is correct
10 Correct 466 ms 11672 KB Output is correct
11 Correct 367 ms 11668 KB Output is correct
12 Correct 442 ms 11732 KB Output is correct
13 Correct 268 ms 8876 KB Output is correct
14 Correct 242 ms 7984 KB Output is correct
15 Correct 350 ms 8892 KB Output is correct
16 Correct 213 ms 7984 KB Output is correct
17 Correct 237 ms 8884 KB Output is correct
18 Correct 218 ms 8000 KB Output is correct
19 Correct 439 ms 10632 KB Output is correct
20 Correct 352 ms 11252 KB Output is correct
21 Correct 616 ms 11712 KB Output is correct
22 Correct 469 ms 11664 KB Output is correct
23 Correct 425 ms 11648 KB Output is correct
24 Correct 434 ms 11668 KB Output is correct
25 Correct 439 ms 11556 KB Output is correct
26 Correct 324 ms 11704 KB Output is correct
27 Correct 152 ms 10412 KB Output is correct
28 Correct 370 ms 10276 KB Output is correct
29 Correct 236 ms 10548 KB Output is correct
30 Correct 144 ms 10416 KB Output is correct
31 Correct 262 ms 10440 KB Output is correct
32 Correct 189 ms 10388 KB Output is correct
33 Correct 202 ms 10520 KB Output is correct
34 Correct 192 ms 10344 KB Output is correct
35 Correct 335 ms 10424 KB Output is correct
36 Correct 254 ms 10224 KB Output is correct
37 Correct 351 ms 10480 KB Output is correct
38 Correct 298 ms 10464 KB Output is correct
39 Correct 420 ms 11716 KB Output is correct
40 Correct 315 ms 11772 KB Output is correct
41 Correct 225 ms 11648 KB Output is correct
42 Correct 496 ms 11552 KB Output is correct