oj.uz

Submission #102710

# Submission time Handle Problem Language Result Execution time Memory
102710 2019-03-27T06:54:35 Z bert30702 Highway Tolls (IOI18_highway) C++17
51 / 100
 385 ms 63724 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);
			}
		}
	}
	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 ++) cout << query[i] << ' '; cout << endl;
			for(int i = 0; i < u.size(); i ++) {
				if(edge[i]) query[i] = 0;
			}
			// for(int i = 0; i < u.size(); i ++) cout << query[i] << ' '; cout << endl;
			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;
           ~~^~~
highway.cpp:65: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:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:90: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 46 ms 47220 KB Output is correct
2 Correct 44 ms 47296 KB Output is correct
3 Correct 45 ms 47296 KB Output is correct
4 Correct 45 ms 47304 KB Output is correct
5 Correct 45 ms 47304 KB Output is correct
6 Correct 45 ms 47308 KB Output is correct
7 Correct 45 ms 47252 KB Output is correct
8 Correct 45 ms 47272 KB Output is correct
9 Correct 45 ms 47300 KB Output is correct
10 Correct 47 ms 47300 KB Output is correct
11 Correct 45 ms 47352 KB Output is correct
12 Correct 45 ms 47220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47400 KB Output is correct
2 Correct 65 ms 48632 KB Output is correct
3 Correct 246 ms 58952 KB Output is correct
4 Correct 243 ms 58872 KB Output is correct
5 Correct 267 ms 58988 KB Output is correct
6 Correct 270 ms 58944 KB Output is correct
7 Correct 272 ms 58872 KB Output is correct
8 Correct 232 ms 58952 KB Output is correct
9 Correct 244 ms 58948 KB Output is correct
10 Correct 270 ms 58888 KB Output is correct
11 Correct 306 ms 59392 KB Output is correct
12 Correct 310 ms 60916 KB Output is correct
13 Correct 267 ms 60652 KB Output is correct
14 Correct 272 ms 60784 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 49156 KB Output is correct
2 Correct 70 ms 50680 KB Output is correct
3 Correct 106 ms 52468 KB Output is correct
4 Correct 209 ms 61416 KB Output is correct
5 Correct 218 ms 61424 KB Output is correct
6 Correct 215 ms 63140 KB Output is correct
7 Correct 227 ms 63724 KB Output is correct
8 Correct 215 ms 62008 KB Output is correct
9 Correct 219 ms 63020 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47420 KB Output is correct
2 Correct 69 ms 48508 KB Output is correct
3 Correct 199 ms 56512 KB Output is correct
4 Correct 264 ms 58944 KB Output is correct
5 Correct 289 ms 58940 KB Output is correct
6 Correct 255 ms 58952 KB Output is correct
7 Correct 274 ms 58864 KB Output is correct
8 Correct 268 ms 58936 KB Output is correct
9 Correct 256 ms 58924 KB Output is correct
10 Correct 264 ms 58900 KB Output is correct
11 Correct 290 ms 60416 KB Output is correct
12 Correct 296 ms 60788 KB Output is correct
13 Correct 295 ms 60912 KB Output is correct
14 Correct 280 ms 59772 KB Output is correct
15 Correct 245 ms 58876 KB Output is correct
16 Correct 258 ms 58896 KB Output is correct
17 Correct 277 ms 60548 KB Output is correct
18 Correct 273 ms 60916 KB Output is correct
19 Correct 265 ms 58940 KB Output is correct
20 Correct 283 ms 61024 KB Output is correct
21 Correct 217 ms 59036 KB Output is correct
22 Correct 192 ms 58940 KB Output is correct
23 Correct 235 ms 57148 KB Output is correct
24 Correct 242 ms 57568 KB Output is correct
25 Correct 261 ms 63332 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 48612 KB Output is correct
2 Correct 72 ms 48796 KB Output is correct
3 Correct 277 ms 59692 KB Output is correct
4 Correct 318 ms 60136 KB Output is correct
5 Correct 385 ms 60444 KB Output is correct
6 Incorrect 373 ms 61444 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 71 ms 48640 KB Output is correct
2 Correct 74 ms 48760 KB Output is correct
3 Correct 297 ms 58584 KB Output is correct
4 Incorrect 328 ms 59480 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -