oj.uz

Submission #102720

# Submission time Handle Problem Language Result Execution time Memory
102720 2019-03-27T08:27:38 Z bert30702 Highway Tolls (IOI18_highway) C++17
51 / 100
 393 ms 63736 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];	
		});
		assert(que[0].S == l);
		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];
		});
		assert(que[0].S == l);
		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: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: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 44 ms 47272 KB Output is correct
2 Correct 53 ms 47352 KB Output is correct
3 Correct 46 ms 47304 KB Output is correct
4 Correct 45 ms 47384 KB Output is correct
5 Correct 44 ms 47300 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 44 ms 47228 KB Output is correct
8 Correct 45 ms 47244 KB Output is correct
9 Correct 45 ms 47292 KB Output is correct
10 Correct 44 ms 47224 KB Output is correct
11 Correct 44 ms 47304 KB Output is correct
12 Correct 44 ms 47300 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47380 KB Output is correct
2 Correct 82 ms 48604 KB Output is correct
3 Correct 276 ms 58948 KB Output is correct
4 Correct 273 ms 58876 KB Output is correct
5 Correct 261 ms 58984 KB Output is correct
6 Correct 257 ms 58944 KB Output is correct
7 Correct 263 ms 58936 KB Output is correct
8 Correct 266 ms 58944 KB Output is correct
9 Correct 255 ms 58896 KB Output is correct
10 Correct 274 ms 58992 KB Output is correct
11 Correct 307 ms 59332 KB Output is correct
12 Correct 299 ms 60920 KB Output is correct
13 Correct 293 ms 60724 KB Output is correct
14 Correct 313 ms 60772 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 49212 KB Output is correct
2 Correct 85 ms 50680 KB Output is correct
3 Correct 90 ms 52580 KB Output is correct
4 Correct 247 ms 61372 KB Output is correct
5 Correct 216 ms 61472 KB Output is correct
6 Correct 226 ms 63152 KB Output is correct
7 Correct 224 ms 63736 KB Output is correct
8 Correct 229 ms 62020 KB Output is correct
9 Correct 238 ms 62976 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47400 KB Output is correct
2 Correct 69 ms 48504 KB Output is correct
3 Correct 200 ms 56476 KB Output is correct
4 Correct 272 ms 58932 KB Output is correct
5 Correct 254 ms 58956 KB Output is correct
6 Correct 279 ms 58940 KB Output is correct
7 Correct 251 ms 58948 KB Output is correct
8 Correct 213 ms 58908 KB Output is correct
9 Correct 259 ms 58936 KB Output is correct
10 Correct 277 ms 58948 KB Output is correct
11 Correct 313 ms 60400 KB Output is correct
12 Correct 286 ms 60780 KB Output is correct
13 Correct 284 ms 60912 KB Output is correct
14 Correct 318 ms 59736 KB Output is correct
15 Correct 252 ms 58956 KB Output is correct
16 Correct 255 ms 58944 KB Output is correct
17 Correct 289 ms 60548 KB Output is correct
18 Correct 282 ms 60924 KB Output is correct
19 Correct 260 ms 58968 KB Output is correct
20 Correct 273 ms 61052 KB Output is correct
21 Correct 228 ms 58944 KB Output is correct
22 Correct 214 ms 59152 KB Output is correct
23 Correct 235 ms 57128 KB Output is correct
24 Correct 194 ms 57552 KB Output is correct
25 Correct 282 ms 63256 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 48612 KB Output is correct
2 Correct 68 ms 48796 KB Output is correct
3 Correct 288 ms 59668 KB Output is correct
4 Correct 322 ms 60148 KB Output is correct
5 Correct 393 ms 60448 KB Output is correct
6 Incorrect 335 ms 61468 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 68 ms 48524 KB Output is correct
2 Correct 85 ms 48784 KB Output is correct
3 Correct 307 ms 58584 KB Output is correct
4 Incorrect 322 ms 59440 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -