oj.uz

Submission #102712

# Submission time Handle Problem Language Result Execution time Memory
102712 2019-03-27T07:32:05 Z bert30702 Highway Tolls (IOI18_highway) C++17
51 / 100
 388 ms 63784 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];
//void answer(int a, int b) {
//	cout << "! " << a << ' ' << b;
//}
//int ask(vector<int32_t> v) {
//	for(auto it: v) cout << it << ' '; cout << endl;
//	int val; cin >> val; return val;
//}
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)) / a;
	int l = 0, r = u.size() - 1;
	while(l != r) {
		int m = l + r >> 1;
		vector<int32_t> query(u.size(), 0);
		for(int j = l; j <= m; j ++) query[j] = 1;
		if(ask(query) > d * a) r = m;
		else                   l = m + 1;
	}
	pass[u[l]] = pass[v[l]] = edge[l] = true;
	queue<pii> q;
	q.push({u[l], l});
	q.push({v[l], l});
	while(q.size()) {
		pii p = q.front(); q.pop();
		for(auto i: G1[p.F]) {
			if(!pass[i.F]) {
				edge[i.S] = true;
				pass[i.F] = true;
				G2[p.F].push_back(i);
				q.push(i);
			}
		}
	}
	assert(edge.count() == n - 1);
	int x, y;
	{
		que.clear();
		dfs(u[l], 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 * a) l = m + 1;
			else                   r = m;
		}
		x = que[l].F;
	}
	{
		que.clear();
		dfs(v[l], 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 * a) l = m + 1;
			else                   r = m;
		}
		y = que[l].F;
	}
	answer(x, y);
}
//main () {
//	find_pair(6, {0, 2, 1, 1, 2, 0}, {1, 4, 2, 5, 3, 5}, 1, 2);
//}

Compilation message

highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i ++) {
                 ~~^~~~~~~~~~
highway.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:1:
highway.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(edge.count() == n - 1);
         ~~~~~~~~~~~~~^~~~~~~~
highway.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~
highway.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:89: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 44 ms 47224 KB Output is correct
2 Correct 44 ms 47224 KB Output is correct
3 Correct 44 ms 47296 KB Output is correct
4 Correct 45 ms 47312 KB Output is correct
5 Correct 45 ms 47300 KB Output is correct
6 Correct 45 ms 47272 KB Output is correct
7 Correct 44 ms 47224 KB Output is correct
8 Correct 44 ms 47224 KB Output is correct
9 Correct 44 ms 47396 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47272 KB Output is correct
12 Correct 44 ms 47224 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47364 KB Output is correct
2 Correct 67 ms 48644 KB Output is correct
3 Correct 236 ms 58948 KB Output is correct
4 Correct 263 ms 58880 KB Output is correct
5 Correct 281 ms 58940 KB Output is correct
6 Correct 251 ms 58944 KB Output is correct
7 Correct 272 ms 58884 KB Output is correct
8 Correct 261 ms 58980 KB Output is correct
9 Correct 249 ms 58956 KB Output is correct
10 Correct 274 ms 58888 KB Output is correct
11 Correct 288 ms 59388 KB Output is correct
12 Correct 350 ms 60912 KB Output is correct
13 Correct 301 ms 60716 KB Output is correct
14 Correct 308 ms 60792 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 49212 KB Output is correct
2 Correct 84 ms 50644 KB Output is correct
3 Correct 102 ms 52556 KB Output is correct
4 Correct 232 ms 61480 KB Output is correct
5 Correct 221 ms 61488 KB Output is correct
6 Correct 219 ms 63128 KB Output is correct
7 Correct 215 ms 63784 KB Output is correct
8 Correct 217 ms 62076 KB Output is correct
9 Correct 212 ms 63044 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47400 KB Output is correct
2 Correct 66 ms 48424 KB Output is correct
3 Correct 207 ms 56528 KB Output is correct
4 Correct 235 ms 58944 KB Output is correct
5 Correct 250 ms 58960 KB Output is correct
6 Correct 262 ms 58944 KB Output is correct
7 Correct 258 ms 58952 KB Output is correct
8 Correct 268 ms 58884 KB Output is correct
9 Correct 272 ms 58948 KB Output is correct
10 Correct 265 ms 58936 KB Output is correct
11 Correct 270 ms 60408 KB Output is correct
12 Correct 304 ms 60784 KB Output is correct
13 Correct 292 ms 60868 KB Output is correct
14 Correct 304 ms 59772 KB Output is correct
15 Correct 265 ms 58988 KB Output is correct
16 Correct 256 ms 58952 KB Output is correct
17 Correct 307 ms 60548 KB Output is correct
18 Correct 289 ms 60920 KB Output is correct
19 Correct 272 ms 58936 KB Output is correct
20 Correct 289 ms 61016 KB Output is correct
21 Correct 229 ms 59060 KB Output is correct
22 Correct 221 ms 59156 KB Output is correct
23 Correct 223 ms 57124 KB Output is correct
24 Correct 223 ms 57684 KB Output is correct
25 Correct 275 ms 63336 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 48524 KB Output is correct
2 Correct 76 ms 48888 KB Output is correct
3 Correct 308 ms 59692 KB Output is correct
4 Correct 335 ms 60144 KB Output is correct
5 Correct 388 ms 60448 KB Output is correct
6 Incorrect 376 ms 61472 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 48588 KB Output is correct
2 Correct 71 ms 48788 KB Output is correct
3 Correct 313 ms 58584 KB Output is correct
4 Incorrect 312 ms 59504 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -