oj.uz

Submission #96702

# Submission time Handle Problem Language Result Execution time Memory
96702 2019-02-11T05:49:01 Z diamond_duke Highway Tolls (IOI18_highway) C++11
100 / 100
 352 ms 10584 KB 
#include "highway.h"
void find_pair(int n, std::vector<int> eu, std::vector<int> ev, int, int)
{
	auto dis = ask(std::vector<int>(eu.size()));
	auto find_edge = [&]
	{
		int l = 0, r = (int)eu.size() - 1, res = -1;
		while (l <= r)
		{
			int m = l + r >> 1;
			std::vector<int> vec(eu.size());
			for (int i = 0; i <= m; i++)
				vec[i] = 1;
			if (ask(vec) > dis)
			{
				res = m;
				r = m - 1;
			}
			else
				l = m + 1;
		}
		return res;
	};
	std::vector<std::vector<int> > adj(n);
	for (int i = 0; i < eu.size(); i++)
	{
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	int e_sp = find_edge();
	std::vector<int> vec_l = {eu[e_sp]}, vec_r = {ev[e_sp]};
	std::vector<int> bel(n, -1), tree = {e_sp}, que = {eu[e_sp], ev[e_sp]};
	bel[eu[e_sp]] = 0;
	bel[ev[e_sp]] = 1;
	for (int he = 0; he < que.size(); he++)
	{
		int u = que[he];
		for (int e : adj[u])
		{
			int v = eu[e] ^ ev[e] ^ u;
			if (~bel[v])
				continue;
			tree.push_back(e);
			que.push_back(v);
			bel[v] = bel[u];
			(bel[v] ? vec_r : vec_l).push_back(v);
		}
	}
	auto solve = [&] (std::vector<int> &node)
	{
		std::vector<int> idx(n, -1);
		for (int i = 0; i < node.size(); i++)
			idx[node[i]] = i;
		int l = 0, r = (int)node.size() - 1, res = -1;
		while (l <= r)
		{
			int m = l + r >> 1;
			std::vector<int> vec(eu.size(), 1);
			for (int e : tree)
				vec[e] = idx[eu[e]] >= m || idx[ev[e]] >= m;
			if (ask(vec) == dis)
				r = m - 1;
			else
			{
				res = m;
				l = m + 1;
			}
		}
		return node[res];
	};
	answer(solve(vec_l), solve(vec_r));
}

Compilation message

highway.cpp: In lambda function:
highway.cpp:10:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < eu.size(); i++)
                  ~~^~~~~~~~~~~
highway.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int he = 0; he < que.size(); he++)
                   ~~~^~~~~~~~~~~~
highway.cpp: In lambda function:
highway.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < node.size(); i++)
                   ~~^~~~~~~~~~~~~
highway.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 312 KB Output is correct
6 Correct 2 ms 308 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 ms 304 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 296 KB Output is correct
2 Correct 24 ms 1324 KB Output is correct
3 Correct 221 ms 9220 KB Output is correct
4 Correct 242 ms 9216 KB Output is correct
5 Correct 233 ms 9200 KB Output is correct
6 Correct 220 ms 9216 KB Output is correct
7 Correct 241 ms 9200 KB Output is correct
8 Correct 245 ms 9100 KB Output is correct
9 Correct 185 ms 9188 KB Output is correct
10 Correct 230 ms 9212 KB Output is correct
11 Correct 235 ms 9248 KB Output is correct
12 Correct 246 ms 8860 KB Output is correct
13 Correct 249 ms 9080 KB Output is correct
14 Correct 250 ms 9248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1272 KB Output is correct
2 Correct 66 ms 2256 KB Output is correct
3 Correct 62 ms 3388 KB Output is correct
4 Correct 171 ms 9224 KB Output is correct
5 Correct 173 ms 9264 KB Output is correct
6 Correct 159 ms 9100 KB Output is correct
7 Correct 159 ms 9156 KB Output is correct
8 Correct 183 ms 8828 KB Output is correct
9 Correct 159 ms 9116 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 31 ms 1272 KB Output is correct
3 Correct 136 ms 7152 KB Output is correct
4 Correct 203 ms 9212 KB Output is correct
5 Correct 203 ms 9260 KB Output is correct
6 Correct 196 ms 9212 KB Output is correct
7 Correct 205 ms 9360 KB Output is correct
8 Correct 217 ms 9280 KB Output is correct
9 Correct 225 ms 9268 KB Output is correct
10 Correct 231 ms 9212 KB Output is correct
11 Correct 218 ms 8952 KB Output is correct
12 Correct 232 ms 9504 KB Output is correct
13 Correct 228 ms 9168 KB Output is correct
14 Correct 243 ms 9020 KB Output is correct
15 Correct 271 ms 9216 KB Output is correct
16 Correct 197 ms 9220 KB Output is correct
17 Correct 236 ms 8856 KB Output is correct
18 Correct 233 ms 9240 KB Output is correct
19 Correct 211 ms 9200 KB Output is correct
20 Correct 218 ms 9116 KB Output is correct
21 Correct 183 ms 9456 KB Output is correct
22 Correct 184 ms 9544 KB Output is correct
23 Correct 189 ms 9560 KB Output is correct
24 Correct 222 ms 9516 KB Output is correct
25 Correct 246 ms 9332 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1232 KB Output is correct
2 Correct 53 ms 1248 KB Output is correct
3 Correct 260 ms 9456 KB Output is correct
4 Correct 294 ms 10024 KB Output is correct
5 Correct 327 ms 10584 KB Output is correct
6 Correct 342 ms 10240 KB Output is correct
7 Correct 321 ms 10220 KB Output is correct
8 Correct 343 ms 10540 KB Output is correct
9 Correct 250 ms 5956 KB Output is correct
10 Correct 251 ms 6208 KB Output is correct
11 Correct 272 ms 7224 KB Output is correct
12 Correct 313 ms 8816 KB Output is correct
13 Correct 304 ms 9600 KB Output is correct
14 Correct 352 ms 10376 KB Output is correct
15 Correct 339 ms 9980 KB Output is correct
16 Correct 282 ms 7124 KB Output is correct
17 Correct 199 ms 9560 KB Output is correct
18 Correct 216 ms 9512 KB Output is correct
19 Correct 223 ms 9536 KB Output is correct
20 Correct 232 ms 9764 KB Output is correct
21 Correct 319 ms 10552 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1232 KB Output is correct
2 Correct 23 ms 1292 KB Output is correct
3 Correct 271 ms 9864 KB Output is correct
4 Correct 267 ms 9876 KB Output is correct
5 Correct 282 ms 9660 KB Output is correct
6 Correct 349 ms 10548 KB Output is correct
7 Correct 243 ms 9468 KB Output is correct
8 Correct 263 ms 9640 KB Output is correct
9 Correct 258 ms 9952 KB Output is correct
10 Correct 334 ms 10400 KB Output is correct
11 Correct 329 ms 10504 KB Output is correct
12 Correct 332 ms 10368 KB Output is correct
13 Correct 252 ms 7040 KB Output is correct
14 Correct 232 ms 6188 KB Output is correct
15 Correct 221 ms 6940 KB Output is correct
16 Correct 241 ms 6116 KB Output is correct
17 Correct 264 ms 7140 KB Output is correct
18 Correct 243 ms 6088 KB Output is correct
19 Correct 318 ms 9120 KB Output is correct
20 Correct 325 ms 9572 KB Output is correct
21 Correct 322 ms 10420 KB Output is correct
22 Correct 331 ms 10160 KB Output is correct
23 Correct 346 ms 10232 KB Output is correct
24 Correct 297 ms 10020 KB Output is correct
25 Correct 340 ms 10428 KB Output is correct
26 Correct 325 ms 10476 KB Output is correct
27 Correct 234 ms 9612 KB Output is correct
28 Correct 215 ms 9536 KB Output is correct
29 Correct 214 ms 9708 KB Output is correct
30 Correct 181 ms 9696 KB Output is correct
31 Correct 233 ms 9760 KB Output is correct
32 Correct 245 ms 9712 KB Output is correct
33 Correct 228 ms 9804 KB Output is correct
34 Correct 249 ms 9580 KB Output is correct
35 Correct 198 ms 9504 KB Output is correct
36 Correct 220 ms 9660 KB Output is correct
37 Correct 230 ms 9752 KB Output is correct
38 Correct 216 ms 9644 KB Output is correct
39 Correct 322 ms 10164 KB Output is correct
40 Correct 325 ms 10296 KB Output is correct
41 Correct 334 ms 10212 KB Output is correct
42 Correct 327 ms 10044 KB Output is correct