oj.uz

Submission #301644

# Submission time Handle Problem Language Result Execution time Memory
301644 2020-09-18T05:40:26 Z square1001 Highway Tolls (IOI18_highway) C++14
100 / 100
 352 ms 15264 KB 
#include "highway.h"
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
vector<int> shortest_path(int src, const vector<vector<int> > &G) {
	int N = G.size();
	queue<int> que;
	que.push(src);
	vector<int> dist(N, inf);
	dist[src] = 0;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i : G[u]) {
			if(dist[i] == inf) {
				dist[i] = dist[u] + 1;
				que.push(i);
			}
		}
	}
	return dist;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	// subtask 1, 2, 3, 4, 5, 6 (90 points)
	// step #0. calculate basic distance
	int M = U.size();
	int D = ask(vector<int>(M, 0)) / A;
	// step #1. binary search connectivity
	int lt = -1, rt = N;
	while(rt - lt > 1) {
		int mt = (lt + rt) >> 1;
		if(lt == -1 && rt == N && N >= 65535) mt = 65534;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			w[i] = (U[i] <= mt && V[i] <= mt ? 0 : 1);
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rt = mt;
		else lt = mt;
	}
	int cutvert = rt;
	// step #2. find either S or T
	vector<vector<int> > G2(cutvert + 1);
	for(int i = 0; i < M; ++i) {
		if(U[i] <= cutvert && V[i] <= cutvert) {
			G2[U[i]].push_back(V[i]);
			G2[V[i]].push_back(U[i]);
		}
	}
	vector<int> dc = shortest_path(cutvert, G2);
	vector<int> perm(cutvert + 1);
	for(int i = 0; i <= cutvert; ++i) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return dc[i] != dc[j] ? dc[i] < dc[j] : i < j; });
	vector<int> iperm(cutvert + 1);
	for(int i = 0; i <= cutvert; ++i) {
		iperm[perm[i]] = i;
	}
	int ls = -1, rs = cutvert + 1;
	while(rs - ls > 1) {
		int ms = (ls + rs) >> 1;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			if(U[i] <= cutvert && V[i] <= cutvert && iperm[U[i]] <= ms && iperm[V[i]] <= ms) {
				w[i] = 0;
			}
			else {
				w[i] = 1;
			}
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rs = ms;
		else ls = ms;
	}
	int S = perm[rs];
	// step #3. find both S and T
	vector<vector<int> > G3(cutvert + 1);
	for(int i = 0; i < M; ++i) {
		if(U[i] <= cutvert && V[i] <= cutvert && iperm[U[i]] <= iperm[S] && iperm[V[i]] <= iperm[S]) {
			G3[U[i]].push_back(V[i]);
			G3[V[i]].push_back(U[i]);
		}
	}
	vector<int> ds = shortest_path(S, G3);
	vector<int> perm2;
	for(int i = 0; i <= cutvert; ++i) {
		if(iperm[i] <= iperm[S]) {
			perm2.push_back(i);
		}
	}
	sort(perm2.begin(), perm2.end(), [&](int i, int j) { return ds[i] != ds[j] ? ds[i] < ds[j] : i < j; });
	vector<int> iperm2(cutvert + 1);
	for(int i = 0; i < int(perm2.size()); ++i) {
		iperm2[perm2[i]] = i;
	}
	int lg = -1, rg = perm2.size() + 1;
	while(rg - lg > 1) {
		int mg = (lg + rg) >> 1;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			if(U[i] <= cutvert && V[i] <= cutvert && iperm2[U[i]] <= mg && iperm2[V[i]] <= mg) {
				w[i] = 0;
			}
			else {
				w[i] = 1;
			}
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rg = mg;
		else lg = mg;
	}
	int T = perm2[rg];
	answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 408 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 17 ms 1536 KB Output is correct
3 Correct 207 ms 13048 KB Output is correct
4 Correct 199 ms 13532 KB Output is correct
5 Correct 174 ms 10284 KB Output is correct
6 Correct 200 ms 13404 KB Output is correct
7 Correct 170 ms 9556 KB Output is correct
8 Correct 187 ms 11756 KB Output is correct
9 Correct 161 ms 10488 KB Output is correct
10 Correct 191 ms 10688 KB Output is correct
11 Correct 172 ms 11424 KB Output is correct
12 Correct 186 ms 12056 KB Output is correct
13 Correct 170 ms 11724 KB Output is correct
14 Correct 214 ms 12920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 27 ms 1600 KB Output is correct
3 Correct 39 ms 3520 KB Output is correct
4 Correct 126 ms 7884 KB Output is correct
5 Correct 117 ms 5420 KB Output is correct
6 Correct 125 ms 11840 KB Output is correct
7 Correct 124 ms 10412 KB Output is correct
8 Correct 130 ms 9200 KB Output is correct
9 Correct 123 ms 9004 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 16 ms 1536 KB Output is correct
3 Correct 121 ms 8612 KB Output is correct
4 Correct 157 ms 10220 KB Output is correct
5 Correct 142 ms 9648 KB Output is correct
6 Correct 157 ms 10856 KB Output is correct
7 Correct 141 ms 10072 KB Output is correct
8 Correct 156 ms 9860 KB Output is correct
9 Correct 199 ms 12860 KB Output is correct
10 Correct 193 ms 11488 KB Output is correct
11 Correct 207 ms 12752 KB Output is correct
12 Correct 211 ms 14052 KB Output is correct
13 Correct 191 ms 12208 KB Output is correct
14 Correct 188 ms 12100 KB Output is correct
15 Correct 147 ms 9820 KB Output is correct
16 Correct 150 ms 10072 KB Output is correct
17 Correct 221 ms 13016 KB Output is correct
18 Correct 171 ms 11700 KB Output is correct
19 Correct 145 ms 8852 KB Output is correct
20 Correct 153 ms 11088 KB Output is correct
21 Correct 186 ms 11956 KB Output is correct
22 Correct 181 ms 12164 KB Output is correct
23 Correct 194 ms 14624 KB Output is correct
24 Correct 186 ms 14576 KB Output is correct
25 Correct 214 ms 14244 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1656 KB Output is correct
2 Correct 18 ms 1656 KB Output is correct
3 Correct 200 ms 11040 KB Output is correct
4 Correct 212 ms 10912 KB Output is correct
5 Correct 294 ms 11692 KB Output is correct
6 Correct 299 ms 12600 KB Output is correct
7 Correct 267 ms 12784 KB Output is correct
8 Correct 275 ms 11740 KB Output is correct
9 Correct 247 ms 8308 KB Output is correct
10 Correct 192 ms 6304 KB Output is correct
11 Correct 225 ms 9604 KB Output is correct
12 Correct 248 ms 9908 KB Output is correct
13 Correct 276 ms 11072 KB Output is correct
14 Correct 293 ms 12164 KB Output is correct
15 Correct 286 ms 11548 KB Output is correct
16 Correct 324 ms 8844 KB Output is correct
17 Correct 238 ms 13932 KB Output is correct
18 Correct 201 ms 11680 KB Output is correct
19 Correct 201 ms 13512 KB Output is correct
20 Correct 207 ms 14072 KB Output is correct
21 Correct 308 ms 12316 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1660 KB Output is correct
2 Correct 28 ms 1656 KB Output is correct
3 Correct 236 ms 8328 KB Output is correct
4 Correct 287 ms 13076 KB Output is correct
5 Correct 249 ms 11812 KB Output is correct
6 Correct 301 ms 14060 KB Output is correct
7 Correct 167 ms 10276 KB Output is correct
8 Correct 210 ms 11228 KB Output is correct
9 Correct 254 ms 10608 KB Output is correct
10 Correct 242 ms 9868 KB Output is correct
11 Correct 236 ms 11476 KB Output is correct
12 Correct 247 ms 8600 KB Output is correct
13 Correct 240 ms 7572 KB Output is correct
14 Correct 190 ms 3908 KB Output is correct
15 Correct 253 ms 7232 KB Output is correct
16 Correct 177 ms 3824 KB Output is correct
17 Correct 303 ms 9116 KB Output is correct
18 Correct 224 ms 4948 KB Output is correct
19 Correct 352 ms 11152 KB Output is correct
20 Correct 244 ms 8912 KB Output is correct
21 Correct 327 ms 12876 KB Output is correct
22 Correct 278 ms 12168 KB Output is correct
23 Correct 266 ms 11892 KB Output is correct
24 Correct 290 ms 11640 KB Output is correct
25 Correct 230 ms 10732 KB Output is correct
26 Correct 221 ms 11072 KB Output is correct
27 Correct 188 ms 13716 KB Output is correct
28 Correct 172 ms 11696 KB Output is correct
29 Correct 192 ms 11152 KB Output is correct
30 Correct 186 ms 12240 KB Output is correct
31 Correct 189 ms 12308 KB Output is correct
32 Correct 177 ms 10240 KB Output is correct
33 Correct 174 ms 12312 KB Output is correct
34 Correct 176 ms 9020 KB Output is correct
35 Correct 187 ms 12768 KB Output is correct
36 Correct 176 ms 13648 KB Output is correct
37 Correct 193 ms 13828 KB Output is correct
38 Correct 203 ms 14636 KB Output is correct
39 Correct 254 ms 12856 KB Output is correct
40 Correct 277 ms 12724 KB Output is correct
41 Correct 288 ms 15264 KB Output is correct
42 Correct 236 ms 12764 KB Output is correct