oj.uz

Submission #74974

# Submission time Handle Problem Language Result Execution time Memory
74974 2018-09-07T19:00:51 Z khsoo01 Highway Tolls (IOI18_highway) C++11
100 / 100
 455 ms 21500 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 90005, M = 1300005;
const ll inf = 1e18;

int n, m, a, b, p;
ll def, dis[N];
bool ban[N], v1[N], v2[N];

vector<int> adj[N], dij[N], drv[N], ord;
vector<pii> edg;

queue<int> q;

ll query () {
	vector<int> V;
	for(int i=0;i<m;i++) {
		V.push_back(ban[edg[i].X] || ban[edg[i].Y]);
	}
	return ask(V);
}

int getpiv () {
	int S = 0, E = (int)ord.size() - 1;
	while(S<E) {
		int Z = (S+E)/2;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = true;
		}
		query() != def ? E = Z : S = Z+1;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = false;
		}
	}
	return ord[S];
}

void dfs1 (int C) {
	if(C == p || v1[C]) return;
	v1[C] = true;
	for(auto &T : drv[C]) {
		dfs1(T);
	}
}

void dfs2 (int C) {
	if(v2[C]) return;
	v2[C] = true;
	for(auto &T : dij[C]) {
		dfs2(T);
	}
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B) {
	n = _N;
	m = (int)_U.size();
	a = _A;
	b = _B;
	for(int i=0;i<m;i++) {
		edg.push_back({_U[i]+1, _V[i]+1});
		adj[_U[i]+1].push_back(_V[i]+1);
		adj[_V[i]+1].push_back(_U[i]+1);
	}
	def = query();
	for(int i=1;i<=n;i++) {
		ord.push_back(i);
	}
	p = getpiv();
	ord.clear();
	for(int i=1;i<p;i++) {
		ban[i] = true;
	}
	for(int i=1;i<=n;i++) {
		dis[i] = inf;
	}
	dis[p] = 0;
	q.push(p);
	while(!q.empty()) {
		int C = q.front();
		q.pop();
		ord.push_back(C);
		for(auto &T : adj[C]) {
			if(T < p) continue;
			if(dis[T] == inf) {
				dis[T] = dis[C] + 1;
				q.push(T);
			}
			if(dis[T] == dis[C] - 1) {
				dij[T].push_back(C);
				drv[C].push_back(T);
			}
		}
	}
	reverse(ord.begin(), ord.end());
	int PA = getpiv();
	ord.clear();
	dfs1(PA);
	for(int i=p;i<=n;i++) {
		if(v1[i]) dfs2(i);
	}
	for(int i=p;i<=n;i++) {
		if(!v2[i] && dis[i] + dis[PA] == def / a) ord.push_back(i);
	}
	int PB = getpiv();
	ord.clear();
	answer(PA-1, PB-1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6756 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6568 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6676 KB Output is correct
7 Correct 8 ms 6692 KB Output is correct
8 Correct 8 ms 6688 KB Output is correct
9 Correct 8 ms 6676 KB Output is correct
10 Correct 8 ms 6692 KB Output is correct
11 Correct 8 ms 6720 KB Output is correct
12 Correct 8 ms 6680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6808 KB Output is correct
2 Correct 29 ms 7972 KB Output is correct
3 Correct 270 ms 17984 KB Output is correct
4 Correct 249 ms 18028 KB Output is correct
5 Correct 298 ms 18028 KB Output is correct
6 Correct 245 ms 17976 KB Output is correct
7 Correct 268 ms 18032 KB Output is correct
8 Correct 270 ms 18032 KB Output is correct
9 Correct 270 ms 17948 KB Output is correct
10 Correct 344 ms 17988 KB Output is correct
11 Correct 295 ms 19308 KB Output is correct
12 Correct 323 ms 19516 KB Output is correct
13 Correct 272 ms 19340 KB Output is correct
14 Correct 280 ms 19180 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8288 KB Output is correct
2 Correct 40 ms 9716 KB Output is correct
3 Correct 51 ms 9196 KB Output is correct
4 Correct 157 ms 18076 KB Output is correct
5 Correct 283 ms 18228 KB Output is correct
6 Correct 301 ms 19712 KB Output is correct
7 Correct 139 ms 14124 KB Output is correct
8 Correct 156 ms 18904 KB Output is correct
9 Correct 141 ms 15104 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6812 KB Output is correct
2 Correct 29 ms 7956 KB Output is correct
3 Correct 175 ms 14288 KB Output is correct
4 Correct 231 ms 15080 KB Output is correct
5 Correct 236 ms 16764 KB Output is correct
6 Correct 310 ms 14072 KB Output is correct
7 Correct 245 ms 15600 KB Output is correct
8 Correct 291 ms 15096 KB Output is correct
9 Correct 267 ms 17316 KB Output is correct
10 Correct 262 ms 17784 KB Output is correct
11 Correct 195 ms 15208 KB Output is correct
12 Correct 220 ms 18288 KB Output is correct
13 Correct 242 ms 18236 KB Output is correct
14 Correct 372 ms 17580 KB Output is correct
15 Correct 217 ms 16876 KB Output is correct
16 Correct 315 ms 14860 KB Output is correct
17 Correct 241 ms 17968 KB Output is correct
18 Correct 301 ms 14856 KB Output is correct
19 Correct 175 ms 13988 KB Output is correct
20 Correct 191 ms 14092 KB Output is correct
21 Correct 251 ms 16324 KB Output is correct
22 Correct 199 ms 15404 KB Output is correct
23 Correct 274 ms 17368 KB Output is correct
24 Correct 249 ms 17840 KB Output is correct
25 Correct 312 ms 21500 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7992 KB Output is correct
2 Correct 26 ms 8048 KB Output is correct
3 Correct 281 ms 18160 KB Output is correct
4 Correct 450 ms 18108 KB Output is correct
5 Correct 355 ms 19224 KB Output is correct
6 Correct 393 ms 18888 KB Output is correct
7 Correct 341 ms 19172 KB Output is correct
8 Correct 350 ms 19360 KB Output is correct
9 Correct 239 ms 13804 KB Output is correct
10 Correct 226 ms 13808 KB Output is correct
11 Correct 212 ms 13620 KB Output is correct
12 Correct 309 ms 17280 KB Output is correct
13 Correct 306 ms 18604 KB Output is correct
14 Correct 352 ms 19408 KB Output is correct
15 Correct 454 ms 19448 KB Output is correct
16 Correct 264 ms 15672 KB Output is correct
17 Correct 223 ms 16896 KB Output is correct
18 Correct 255 ms 16764 KB Output is correct
19 Correct 225 ms 17384 KB Output is correct
20 Correct 363 ms 16072 KB Output is correct
21 Correct 328 ms 20004 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8004 KB Output is correct
2 Correct 26 ms 7988 KB Output is correct
3 Correct 254 ms 17696 KB Output is correct
4 Correct 271 ms 18316 KB Output is correct
5 Correct 295 ms 17912 KB Output is correct
6 Correct 327 ms 19500 KB Output is correct
7 Correct 278 ms 17948 KB Output is correct
8 Correct 298 ms 18620 KB Output is correct
9 Correct 284 ms 18780 KB Output is correct
10 Correct 315 ms 19620 KB Output is correct
11 Correct 331 ms 19012 KB Output is correct
12 Correct 352 ms 19648 KB Output is correct
13 Correct 327 ms 14356 KB Output is correct
14 Correct 253 ms 15176 KB Output is correct
15 Correct 240 ms 14436 KB Output is correct
16 Correct 263 ms 14596 KB Output is correct
17 Correct 261 ms 13504 KB Output is correct
18 Correct 241 ms 14240 KB Output is correct
19 Correct 305 ms 17720 KB Output is correct
20 Correct 455 ms 18516 KB Output is correct
21 Correct 314 ms 19072 KB Output is correct
22 Correct 329 ms 18900 KB Output is correct
23 Correct 345 ms 19752 KB Output is correct
24 Correct 335 ms 19564 KB Output is correct
25 Correct 325 ms 17572 KB Output is correct
26 Correct 334 ms 19844 KB Output is correct
27 Correct 244 ms 16360 KB Output is correct
28 Correct 217 ms 16200 KB Output is correct
29 Correct 222 ms 16068 KB Output is correct
30 Correct 274 ms 15632 KB Output is correct
31 Correct 256 ms 16512 KB Output is correct
32 Correct 229 ms 15784 KB Output is correct
33 Correct 239 ms 16760 KB Output is correct
34 Correct 213 ms 17360 KB Output is correct
35 Correct 373 ms 17488 KB Output is correct
36 Correct 247 ms 16224 KB Output is correct
37 Correct 260 ms 16132 KB Output is correct
38 Correct 392 ms 16068 KB Output is correct
39 Correct 306 ms 19888 KB Output is correct
40 Correct 342 ms 20140 KB Output is correct
41 Correct 455 ms 19936 KB Output is correct
42 Correct 320 ms 19920 KB Output is correct