oj.uz

Submission #102715

# Submission time Handle Problem Language Result Execution time Memory
102715 2019-03-27T08:12:55 Z bert30702 Highway Tolls (IOI18_highway) C++17
51 / 100
 414 ms 63764 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));
	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) 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 = -1, y = -1;
	{
		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) 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) l = m + 1;
			else               r = m;
		}
		y = que[l].F;
	}
	answer(x, y);
}
//main () {
//	find_pair(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 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:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < u.size(); i ++) {
                   ~~^~~~~~~~~~
highway.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp:88: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 47296 KB Output is correct
3 Correct 44 ms 47304 KB Output is correct
4 Correct 44 ms 47300 KB Output is correct
5 Correct 45 ms 47356 KB Output is correct
6 Correct 45 ms 47300 KB Output is correct
7 Correct 44 ms 47304 KB Output is correct
8 Correct 45 ms 47224 KB Output is correct
9 Correct 46 ms 47236 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 44 ms 47224 KB Output is correct
12 Correct 44 ms 47268 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 65 ms 48632 KB Output is correct
3 Correct 269 ms 58948 KB Output is correct
4 Correct 267 ms 59000 KB Output is correct
5 Correct 248 ms 59028 KB Output is correct
6 Correct 265 ms 58956 KB Output is correct
7 Correct 267 ms 58896 KB Output is correct
8 Correct 268 ms 58992 KB Output is correct
9 Correct 259 ms 58944 KB Output is correct
10 Correct 257 ms 58880 KB Output is correct
11 Correct 283 ms 59384 KB Output is correct
12 Correct 306 ms 60956 KB Output is correct
13 Correct 272 ms 60724 KB Output is correct
14 Correct 279 ms 60788 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 49160 KB Output is correct
2 Correct 79 ms 50684 KB Output is correct
3 Correct 109 ms 52504 KB Output is correct
4 Correct 212 ms 61376 KB Output is correct
5 Correct 234 ms 61468 KB Output is correct
6 Correct 217 ms 63140 KB Output is correct
7 Correct 215 ms 63764 KB Output is correct
8 Correct 196 ms 62020 KB Output is correct
9 Correct 219 ms 63024 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47368 KB Output is correct
2 Correct 65 ms 48648 KB Output is correct
3 Correct 204 ms 56504 KB Output is correct
4 Correct 255 ms 58912 KB Output is correct
5 Correct 282 ms 58892 KB Output is correct
6 Correct 255 ms 58940 KB Output is correct
7 Correct 251 ms 58944 KB Output is correct
8 Correct 255 ms 58888 KB Output is correct
9 Correct 267 ms 58988 KB Output is correct
10 Correct 257 ms 58956 KB Output is correct
11 Correct 286 ms 60416 KB Output is correct
12 Correct 298 ms 60768 KB Output is correct
13 Correct 307 ms 60920 KB Output is correct
14 Correct 298 ms 59772 KB Output is correct
15 Correct 236 ms 59000 KB Output is correct
16 Correct 267 ms 59080 KB Output is correct
17 Correct 278 ms 60544 KB Output is correct
18 Correct 259 ms 60928 KB Output is correct
19 Correct 257 ms 58956 KB Output is correct
20 Correct 286 ms 61024 KB Output is correct
21 Correct 223 ms 59044 KB Output is correct
22 Correct 205 ms 58944 KB Output is correct
23 Correct 228 ms 57120 KB Output is correct
24 Correct 246 ms 57588 KB Output is correct
25 Correct 267 ms 63316 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 48608 KB Output is correct
2 Correct 75 ms 48736 KB Output is correct
3 Correct 279 ms 59636 KB Output is correct
4 Correct 333 ms 60124 KB Output is correct
5 Correct 414 ms 60440 KB Output is correct
6 Incorrect 376 ms 61476 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 48552 KB Output is correct
2 Correct 66 ms 48800 KB Output is correct
3 Correct 315 ms 58592 KB Output is correct
4 Incorrect 320 ms 59404 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -