oj.uz

Submission #74972

# Submission time Handle Problem Language Result Execution time Memory
74972 2018-09-07T18:57:05 Z khsoo01 Highway Tolls (IOI18_highway) C++11
100 / 100
 525 ms 21584 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);
	}
	for(int i=0;i<2;i++) query();
	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 9 ms 6684 KB Output is correct
2 Correct 8 ms 6692 KB Output is correct
3 Correct 8 ms 6684 KB Output is correct
4 Correct 8 ms 6668 KB Output is correct
5 Correct 8 ms 6680 KB Output is correct
6 Correct 8 ms 6752 KB Output is correct
7 Correct 8 ms 6676 KB Output is correct
8 Correct 8 ms 6684 KB Output is correct
9 Correct 8 ms 6672 KB Output is correct
10 Correct 8 ms 6692 KB Output is correct
11 Correct 8 ms 6680 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 9 ms 6776 KB Output is correct
2 Correct 59 ms 7924 KB Output is correct
3 Correct 273 ms 18000 KB Output is correct
4 Correct 266 ms 18056 KB Output is correct
5 Correct 267 ms 18044 KB Output is correct
6 Correct 248 ms 18048 KB Output is correct
7 Correct 252 ms 18052 KB Output is correct
8 Correct 281 ms 18020 KB Output is correct
9 Correct 235 ms 18064 KB Output is correct
10 Correct 253 ms 17996 KB Output is correct
11 Correct 396 ms 19312 KB Output is correct
12 Correct 322 ms 19560 KB Output is correct
13 Correct 272 ms 19304 KB Output is correct
14 Correct 251 ms 19192 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8292 KB Output is correct
2 Correct 38 ms 9720 KB Output is correct
3 Correct 102 ms 9108 KB Output is correct
4 Correct 176 ms 18176 KB Output is correct
5 Correct 170 ms 18224 KB Output is correct
6 Correct 253 ms 19708 KB Output is correct
7 Correct 120 ms 14144 KB Output is correct
8 Correct 170 ms 18900 KB Output is correct
9 Correct 160 ms 15104 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6744 KB Output is correct
2 Correct 39 ms 7956 KB Output is correct
3 Correct 192 ms 14288 KB Output is correct
4 Correct 239 ms 15036 KB Output is correct
5 Correct 267 ms 16728 KB Output is correct
6 Correct 311 ms 14076 KB Output is correct
7 Correct 204 ms 15656 KB Output is correct
8 Correct 335 ms 15044 KB Output is correct
9 Correct 259 ms 17280 KB Output is correct
10 Correct 283 ms 17856 KB Output is correct
11 Correct 213 ms 15188 KB Output is correct
12 Correct 245 ms 18204 KB Output is correct
13 Correct 244 ms 18244 KB Output is correct
14 Correct 253 ms 17580 KB Output is correct
15 Correct 268 ms 16836 KB Output is correct
16 Correct 217 ms 14808 KB Output is correct
17 Correct 239 ms 17968 KB Output is correct
18 Correct 179 ms 14804 KB Output is correct
19 Correct 163 ms 13992 KB Output is correct
20 Correct 308 ms 14048 KB Output is correct
21 Correct 241 ms 16300 KB Output is correct
22 Correct 252 ms 15468 KB Output is correct
23 Correct 244 ms 17428 KB Output is correct
24 Correct 228 ms 17884 KB Output is correct
25 Correct 299 ms 21584 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7992 KB Output is correct
2 Correct 33 ms 8044 KB Output is correct
3 Correct 290 ms 18180 KB Output is correct
4 Correct 334 ms 18072 KB Output is correct
5 Correct 525 ms 19212 KB Output is correct
6 Correct 379 ms 18880 KB Output is correct
7 Correct 484 ms 19192 KB Output is correct
8 Correct 418 ms 19360 KB Output is correct
9 Correct 236 ms 13836 KB Output is correct
10 Correct 433 ms 13816 KB Output is correct
11 Correct 349 ms 13644 KB Output is correct
12 Correct 514 ms 17288 KB Output is correct
13 Correct 329 ms 18608 KB Output is correct
14 Correct 353 ms 19420 KB Output is correct
15 Correct 516 ms 19452 KB Output is correct
16 Correct 334 ms 15680 KB Output is correct
17 Correct 303 ms 16892 KB Output is correct
18 Correct 197 ms 16768 KB Output is correct
19 Correct 382 ms 17360 KB Output is correct
20 Correct 277 ms 16100 KB Output is correct
21 Correct 393 ms 20008 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8008 KB Output is correct
2 Correct 36 ms 7988 KB Output is correct
3 Correct 295 ms 17704 KB Output is correct
4 Correct 302 ms 18332 KB Output is correct
5 Correct 320 ms 17856 KB Output is correct
6 Correct 361 ms 19488 KB Output is correct
7 Correct 289 ms 17956 KB Output is correct
8 Correct 441 ms 18600 KB Output is correct
9 Correct 298 ms 18812 KB Output is correct
10 Correct 434 ms 19672 KB Output is correct
11 Correct 370 ms 19016 KB Output is correct
12 Correct 416 ms 19652 KB Output is correct
13 Correct 254 ms 14384 KB Output is correct
14 Correct 241 ms 15180 KB Output is correct
15 Correct 250 ms 14436 KB Output is correct
16 Correct 429 ms 14596 KB Output is correct
17 Correct 229 ms 13548 KB Output is correct
18 Correct 258 ms 14232 KB Output is correct
19 Correct 280 ms 17672 KB Output is correct
20 Correct 299 ms 18520 KB Output is correct
21 Correct 327 ms 19084 KB Output is correct
22 Correct 336 ms 18936 KB Output is correct
23 Correct 367 ms 19748 KB Output is correct
24 Correct 518 ms 19564 KB Output is correct
25 Correct 336 ms 17548 KB Output is correct
26 Correct 371 ms 19836 KB Output is correct
27 Correct 249 ms 16324 KB Output is correct
28 Correct 201 ms 16200 KB Output is correct
29 Correct 367 ms 16060 KB Output is correct
30 Correct 234 ms 15624 KB Output is correct
31 Correct 224 ms 16504 KB Output is correct
32 Correct 369 ms 15812 KB Output is correct
33 Correct 270 ms 16768 KB Output is correct
34 Correct 223 ms 17396 KB Output is correct
35 Correct 268 ms 17552 KB Output is correct
36 Correct 238 ms 16252 KB Output is correct
37 Correct 244 ms 16120 KB Output is correct
38 Correct 258 ms 16072 KB Output is correct
39 Correct 346 ms 19876 KB Output is correct
40 Correct 347 ms 20224 KB Output is correct
41 Correct 339 ms 19940 KB Output is correct
42 Correct 352 ms 19920 KB Output is correct