oj.uz

Submission #76981

# Submission time Handle Problem Language Result Execution time Memory
76981 2018-09-19T17:51:40 Z gs14004 Highway Tolls (IOI18_highway) C++17
69 / 100
 324 ms 9912 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;
	while(s + 1 != e){
		int m = (s + e) / 2;
		fill(v.begin(), v.end(), 1);
		fill(v.begin() + s, v.begin() + m, 0);
		if(ask(v) > 1ll * B * (stdist - 1) + A) s = m; // no intersection
		else e = m;
	}
	// 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 5 ms 2728 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2820 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2700 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2680 KB Output is correct
11 Correct 6 ms 2728 KB Output is correct
12 Correct 5 ms 2696 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 24 ms 3368 KB Output is correct
3 Correct 181 ms 8460 KB Output is correct
4 Correct 199 ms 8488 KB Output is correct
5 Correct 209 ms 8484 KB Output is correct
6 Correct 192 ms 8352 KB Output is correct
7 Correct 199 ms 8472 KB Output is correct
8 Correct 205 ms 8628 KB Output is correct
9 Correct 192 ms 8636 KB Output is correct
10 Correct 195 ms 8464 KB Output is correct
11 Correct 204 ms 8316 KB Output is correct
12 Correct 203 ms 8364 KB Output is correct
13 Correct 210 ms 8328 KB Output is correct
14 Correct 209 ms 8388 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3452 KB Output is correct
2 Correct 43 ms 4084 KB Output is correct
3 Correct 71 ms 4676 KB Output is correct
4 Correct 163 ms 8272 KB Output is correct
5 Correct 164 ms 8288 KB Output is correct
6 Correct 178 ms 8304 KB Output is correct
7 Correct 183 ms 8612 KB Output is correct
8 Correct 176 ms 8208 KB Output is correct
9 Correct 169 ms 8296 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 27 ms 3320 KB Output is correct
3 Correct 129 ms 7328 KB Output is correct
4 Correct 196 ms 8560 KB Output is correct
5 Correct 142 ms 8580 KB Output is correct
6 Correct 200 ms 8628 KB Output is correct
7 Correct 192 ms 8604 KB Output is correct
8 Correct 181 ms 8588 KB Output is correct
9 Correct 209 ms 8580 KB Output is correct
10 Correct 214 ms 8568 KB Output is correct
11 Correct 173 ms 8360 KB Output is correct
12 Correct 206 ms 8340 KB Output is correct
13 Correct 194 ms 8300 KB Output is correct
14 Correct 202 ms 8296 KB Output is correct
15 Correct 206 ms 8604 KB Output is correct
16 Correct 191 ms 8648 KB Output is correct
17 Correct 191 ms 8340 KB Output is correct
18 Correct 201 ms 8360 KB Output is correct
19 Correct 195 ms 8712 KB Output is correct
20 Correct 208 ms 8440 KB Output is correct
21 Correct 143 ms 9180 KB Output is correct
22 Correct 174 ms 9264 KB Output is correct
23 Correct 220 ms 8928 KB Output is correct
24 Correct 172 ms 8900 KB Output is correct
25 Correct 214 ms 8412 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3452 KB Output is correct
2 Correct 28 ms 3416 KB Output is correct
3 Correct 238 ms 8672 KB Output is correct
4 Correct 268 ms 9024 KB Output is correct
5 Correct 296 ms 9716 KB Output is correct
6 Correct 303 ms 9644 KB Output is correct
7 Correct 308 ms 9704 KB Output is correct
8 Correct 292 ms 9656 KB Output is correct
9 Correct 244 ms 7908 KB Output is correct
10 Correct 265 ms 8544 KB Output is correct
11 Correct 253 ms 8356 KB Output is correct
12 Correct 316 ms 9320 KB Output is correct
13 Correct 283 ms 9432 KB Output is correct
14 Correct 292 ms 9536 KB Output is correct
15 Correct 279 ms 9724 KB Output is correct
16 Correct 324 ms 8696 KB Output is correct
17 Correct 205 ms 9180 KB Output is correct
18 Correct 204 ms 9176 KB Output is correct
19 Correct 237 ms 9400 KB Output is correct
20 Correct 183 ms 9440 KB Output is correct
21 Correct 258 ms 9720 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3456 KB Output is correct
2 Correct 29 ms 3540 KB Output is correct
3 Correct 244 ms 8860 KB Output is correct
4 Correct 241 ms 9088 KB Output is correct
5 Correct 222 ms 9328 KB Output is correct
6 Correct 299 ms 9912 KB Output is correct
7 Correct 222 ms 8980 KB Output is correct
8 Correct 267 ms 9072 KB Output is correct
9 Correct 254 ms 9264 KB Output is correct
10 Incorrect 314 ms 9612 KB Output is incorrect: {s, t} is wrong.
11 Halted 0 ms 0 KB -