oj.uz

Submission #77104

# Submission time Handle Problem Language Result Execution time Memory
77104 2018-09-21T11:59:16 Z gs14004 Highway Tolls (IOI18_highway) C++17
100 / 100
 336 ms 9956 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 90005;

int dist[MAXN];
vector<int> gph[MAXN];

lint cut_ask(int m, vector<int> &c, vector<int> &u, vector<int> &v){
	bitset<MAXN> vis;
	for(auto &i : c) vis[i] = 1;
	vector<int> query(m);
	for(int i=0; i<m; i++){
		if(vis[u[i]] != vis[v[i]]) query[i] = 1;
	}
	return ask(query);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	for(int i=0; i<M; i++){
		gph[U[i]].emplace_back(V[i]);
		gph[V[i]].emplace_back(U[i]); 
	}
	vector<int> v(M);
	int stdist = ask(v) / A;
	int s = 0, e = M - 1;
	while(s != e){
		int m = (s + e) / 2;
		fill(v.begin() + m + 1, v.end(), 0);
		fill(v.begin(), v.begin() + m + 1, 1);
		if(ask(v) != 1ll * A * stdist) e = m; // encloses all spaths
		else s = m + 1;
	}
	// 18 queries till this point
	vector<int> bord[2];
	queue<pi> que;
	que.emplace(0, U[s]);
	que.emplace(1, V[s]);
	memset(dist, 0x3f, sizeof(dist));
	dist[U[s]] = dist[V[s]] = 0;
	while(!que.empty()){
		auto x = que.front(); que.pop();
		bord[x.first].push_back(x.second);
		for(auto &i : gph[x.second]){
			if(dist[i] > dist[x.second] + 1){
				dist[i] = dist[x.second] + 1;
				que.emplace(x.first, i);
			}
		}
	}
	s = 0, e = (int)bord[0].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[0].begin() + m, bord[0].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int S = bord[0][s];
	s = 0, e = (int)bord[1].size() - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		vector<int> C(bord[1].begin() + m, bord[1].end());
		if(cut_ask(M, C, U, V) != 1ll * stdist * A) s = m;
		else e = m - 1;
	}
	int T = bord[1][s];
	answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2708 KB Output is correct
2 Correct 5 ms 2732 KB Output is correct
3 Correct 4 ms 2736 KB Output is correct
4 Correct 4 ms 2696 KB Output is correct
5 Correct 5 ms 2780 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2784 KB Output is correct
8 Correct 5 ms 2708 KB Output is correct
9 Correct 4 ms 2728 KB Output is correct
10 Correct 4 ms 2728 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2824 KB Output is correct
2 Correct 26 ms 3404 KB Output is correct
3 Correct 200 ms 8512 KB Output is correct
4 Correct 193 ms 8484 KB Output is correct
5 Correct 203 ms 8468 KB Output is correct
6 Correct 201 ms 8412 KB Output is correct
7 Correct 203 ms 8476 KB Output is correct
8 Correct 234 ms 8696 KB Output is correct
9 Correct 198 ms 8632 KB Output is correct
10 Correct 194 ms 8472 KB Output is correct
11 Correct 202 ms 8308 KB Output is correct
12 Correct 202 ms 8356 KB Output is correct
13 Correct 230 ms 8248 KB Output is correct
14 Correct 188 ms 8444 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3324 KB Output is correct
2 Correct 36 ms 4080 KB Output is correct
3 Correct 67 ms 4680 KB Output is correct
4 Correct 123 ms 8248 KB Output is correct
5 Correct 181 ms 8328 KB Output is correct
6 Correct 180 ms 8244 KB Output is correct
7 Correct 183 ms 8480 KB Output is correct
8 Correct 168 ms 8248 KB Output is correct
9 Correct 152 ms 8372 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2824 KB Output is correct
2 Correct 25 ms 3448 KB Output is correct
3 Correct 156 ms 7328 KB Output is correct
4 Correct 212 ms 8560 KB Output is correct
5 Correct 189 ms 8592 KB Output is correct
6 Correct 210 ms 8676 KB Output is correct
7 Correct 209 ms 8636 KB Output is correct
8 Correct 202 ms 8580 KB Output is correct
9 Correct 184 ms 8596 KB Output is correct
10 Correct 214 ms 8544 KB Output is correct
11 Correct 196 ms 8448 KB Output is correct
12 Correct 188 ms 8336 KB Output is correct
13 Correct 196 ms 8268 KB Output is correct
14 Correct 205 ms 8320 KB Output is correct
15 Correct 207 ms 8596 KB Output is correct
16 Correct 211 ms 8648 KB Output is correct
17 Correct 193 ms 8324 KB Output is correct
18 Correct 210 ms 8368 KB Output is correct
19 Correct 190 ms 8596 KB Output is correct
20 Correct 208 ms 8444 KB Output is correct
21 Correct 163 ms 9240 KB Output is correct
22 Correct 172 ms 9208 KB Output is correct
23 Correct 187 ms 9024 KB Output is correct
24 Correct 208 ms 8892 KB Output is correct
25 Correct 211 ms 8344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3460 KB Output is correct
2 Correct 41 ms 3424 KB Output is correct
3 Correct 194 ms 8680 KB Output is correct
4 Correct 253 ms 9048 KB Output is correct
5 Correct 292 ms 9956 KB Output is correct
6 Correct 310 ms 9620 KB Output is correct
7 Correct 306 ms 9640 KB Output is correct
8 Correct 287 ms 9608 KB Output is correct
9 Correct 273 ms 7872 KB Output is correct
10 Correct 255 ms 8352 KB Output is correct
11 Correct 259 ms 8428 KB Output is correct
12 Correct 301 ms 9308 KB Output is correct
13 Correct 289 ms 9596 KB Output is correct
14 Correct 292 ms 9544 KB Output is correct
15 Correct 300 ms 9700 KB Output is correct
16 Correct 271 ms 8624 KB Output is correct
17 Correct 197 ms 9156 KB Output is correct
18 Correct 196 ms 9448 KB Output is correct
19 Correct 213 ms 9180 KB Output is correct
20 Correct 195 ms 9488 KB Output is correct
21 Correct 290 ms 9580 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3484 KB Output is correct
2 Correct 30 ms 3496 KB Output is correct
3 Correct 235 ms 8848 KB Output is correct
4 Correct 231 ms 9108 KB Output is correct
5 Correct 264 ms 9320 KB Output is correct
6 Correct 290 ms 9620 KB Output is correct
7 Correct 222 ms 8932 KB Output is correct
8 Correct 257 ms 9104 KB Output is correct
9 Correct 239 ms 9176 KB Output is correct
10 Correct 308 ms 9668 KB Output is correct
11 Correct 308 ms 9728 KB Output is correct
12 Correct 314 ms 9640 KB Output is correct
13 Correct 211 ms 8432 KB Output is correct
14 Correct 271 ms 8328 KB Output is correct
15 Correct 249 ms 8484 KB Output is correct
16 Correct 228 ms 8368 KB Output is correct
17 Correct 254 ms 8376 KB Output is correct
18 Correct 261 ms 8388 KB Output is correct
19 Correct 304 ms 9200 KB Output is correct
20 Correct 280 ms 9516 KB Output is correct
21 Correct 336 ms 9612 KB Output is correct
22 Correct 325 ms 9532 KB Output is correct
23 Correct 296 ms 9672 KB Output is correct
24 Correct 281 ms 9484 KB Output is correct
25 Correct 292 ms 9768 KB Output is correct
26 Correct 287 ms 9776 KB Output is correct
27 Correct 194 ms 9212 KB Output is correct
28 Correct 194 ms 9352 KB Output is correct
29 Correct 207 ms 9456 KB Output is correct
30 Correct 190 ms 9004 KB Output is correct
31 Correct 202 ms 9168 KB Output is correct
32 Correct 218 ms 9320 KB Output is correct
33 Correct 212 ms 9268 KB Output is correct
34 Correct 218 ms 9376 KB Output is correct
35 Correct 199 ms 9348 KB Output is correct
36 Correct 196 ms 9296 KB Output is correct
37 Correct 217 ms 9616 KB Output is correct
38 Correct 174 ms 9352 KB Output is correct
39 Correct 282 ms 9540 KB Output is correct
40 Correct 256 ms 9660 KB Output is correct
41 Correct 211 ms 9460 KB Output is correct
42 Correct 264 ms 9504 KB Output is correct