oj.uz

Submission #102709

# Submission time Handle Problem Language Result Execution time Memory
102709 2019-03-27T06:33:21 Z bert30702 Highway Tolls (IOI18_highway) C++17
51 / 100
 346 ms 20972 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 = 9e4 + 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);
			}
		}
	}
	// for(int i = 0; i < n; i ++) cout << pass[i] << ' '; cout << endl;
	// cout << l << ' ' << u[l] << ' ' << v[l] << endl;
	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];	
		});
		// for(auto it: que) cout << it.F << ',' << it.S << ' '; cout << endl;
		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];	
		});
		// for(auto it: que) cout << it.F << ',' << it.S << ' '; cout << endl;
		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}, {1, 4, 2, 5, 3}, 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;
           ~~^~~
highway.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~
highway.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:92: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 6 ms 4516 KB Output is correct
2 Correct 6 ms 4492 KB Output is correct
3 Correct 6 ms 4600 KB Output is correct
4 Correct 6 ms 4576 KB Output is correct
5 Correct 6 ms 4600 KB Output is correct
6 Correct 6 ms 4648 KB Output is correct
7 Correct 6 ms 4600 KB Output is correct
8 Correct 7 ms 4556 KB Output is correct
9 Correct 6 ms 4668 KB Output is correct
10 Correct 5 ms 4560 KB Output is correct
11 Correct 6 ms 4560 KB Output is correct
12 Correct 6 ms 4472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 49 ms 5956 KB Output is correct
3 Correct 232 ms 16196 KB Output is correct
4 Correct 228 ms 16128 KB Output is correct
5 Correct 225 ms 16172 KB Output is correct
6 Correct 222 ms 16208 KB Output is correct
7 Correct 231 ms 16124 KB Output is correct
8 Correct 229 ms 16220 KB Output is correct
9 Correct 233 ms 16204 KB Output is correct
10 Correct 218 ms 16192 KB Output is correct
11 Correct 251 ms 16524 KB Output is correct
12 Correct 251 ms 18268 KB Output is correct
13 Correct 240 ms 17844 KB Output is correct
14 Correct 259 ms 17920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6548 KB Output is correct
2 Correct 45 ms 8032 KB Output is correct
3 Correct 68 ms 9876 KB Output is correct
4 Correct 161 ms 18624 KB Output is correct
5 Correct 178 ms 18672 KB Output is correct
6 Correct 185 ms 20388 KB Output is correct
7 Correct 182 ms 20972 KB Output is correct
8 Correct 188 ms 19268 KB Output is correct
9 Correct 186 ms 20296 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4648 KB Output is correct
2 Correct 28 ms 5672 KB Output is correct
3 Correct 165 ms 13748 KB Output is correct
4 Correct 227 ms 16164 KB Output is correct
5 Correct 217 ms 16160 KB Output is correct
6 Correct 217 ms 16196 KB Output is correct
7 Correct 219 ms 16200 KB Output is correct
8 Correct 224 ms 16184 KB Output is correct
9 Correct 233 ms 16212 KB Output is correct
10 Correct 207 ms 16200 KB Output is correct
11 Correct 256 ms 17668 KB Output is correct
12 Correct 248 ms 18028 KB Output is correct
13 Correct 225 ms 18052 KB Output is correct
14 Correct 245 ms 16944 KB Output is correct
15 Correct 226 ms 16132 KB Output is correct
16 Correct 209 ms 16216 KB Output is correct
17 Correct 227 ms 17744 KB Output is correct
18 Correct 273 ms 18176 KB Output is correct
19 Correct 207 ms 16160 KB Output is correct
20 Correct 246 ms 18292 KB Output is correct
21 Correct 198 ms 16300 KB Output is correct
22 Correct 154 ms 16204 KB Output is correct
23 Correct 207 ms 14372 KB Output is correct
24 Correct 208 ms 14796 KB Output is correct
25 Correct 238 ms 20592 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5872 KB Output is correct
2 Correct 34 ms 6056 KB Output is correct
3 Correct 252 ms 16664 KB Output is correct
4 Correct 295 ms 16116 KB Output is correct
5 Incorrect 346 ms 17196 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5848 KB Output is correct
2 Correct 34 ms 6048 KB Output is correct
3 Correct 253 ms 15588 KB Output is correct
4 Incorrect 280 ms 16480 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -