oj.uz

Submission #74962

# Submission time Handle Problem Language Result Execution time Memory
74962 2018-09-07T18:42:28 Z khsoo01 Highway Tolls (IOI18_highway) C++11
100 / 100
 528 ms 21576 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 6692 KB Output is correct
2 Correct 8 ms 6672 KB Output is correct
3 Correct 8 ms 6776 KB Output is correct
4 Correct 8 ms 6696 KB Output is correct
5 Correct 8 ms 6696 KB Output is correct
6 Correct 8 ms 6680 KB Output is correct
7 Correct 8 ms 6692 KB Output is correct
8 Correct 8 ms 6696 KB Output is correct
9 Correct 8 ms 6696 KB Output is correct
10 Correct 8 ms 6688 KB Output is correct
11 Correct 8 ms 6676 KB Output is correct
12 Correct 8 ms 6692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6796 KB Output is correct
2 Correct 27 ms 7968 KB Output is correct
3 Correct 269 ms 18000 KB Output is correct
4 Correct 280 ms 18040 KB Output is correct
5 Correct 242 ms 17936 KB Output is correct
6 Correct 305 ms 18020 KB Output is correct
7 Correct 244 ms 18004 KB Output is correct
8 Correct 274 ms 18024 KB Output is correct
9 Correct 246 ms 17984 KB Output is correct
10 Correct 240 ms 18020 KB Output is correct
11 Correct 267 ms 19304 KB Output is correct
12 Correct 236 ms 19576 KB Output is correct
13 Correct 387 ms 19304 KB Output is correct
14 Correct 367 ms 19248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8284 KB Output is correct
2 Correct 41 ms 9668 KB Output is correct
3 Correct 43 ms 9156 KB Output is correct
4 Correct 157 ms 18140 KB Output is correct
5 Correct 166 ms 18228 KB Output is correct
6 Correct 249 ms 19708 KB Output is correct
7 Correct 134 ms 14120 KB Output is correct
8 Correct 294 ms 18912 KB Output is correct
9 Correct 164 ms 15080 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6800 KB Output is correct
2 Correct 35 ms 8012 KB Output is correct
3 Correct 158 ms 14280 KB Output is correct
4 Correct 223 ms 15048 KB Output is correct
5 Correct 247 ms 16724 KB Output is correct
6 Correct 187 ms 14076 KB Output is correct
7 Correct 360 ms 15600 KB Output is correct
8 Correct 252 ms 15056 KB Output is correct
9 Correct 251 ms 17284 KB Output is correct
10 Correct 380 ms 17836 KB Output is correct
11 Correct 216 ms 15160 KB Output is correct
12 Correct 278 ms 18212 KB Output is correct
13 Correct 371 ms 18244 KB Output is correct
14 Correct 284 ms 17496 KB Output is correct
15 Correct 219 ms 16824 KB Output is correct
16 Correct 189 ms 14824 KB Output is correct
17 Correct 247 ms 17976 KB Output is correct
18 Correct 307 ms 14812 KB Output is correct
19 Correct 172 ms 14004 KB Output is correct
20 Correct 191 ms 14088 KB Output is correct
21 Correct 371 ms 16288 KB Output is correct
22 Correct 337 ms 15452 KB Output is correct
23 Correct 233 ms 17344 KB Output is correct
24 Correct 307 ms 17872 KB Output is correct
25 Correct 420 ms 21576 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7988 KB Output is correct
2 Correct 35 ms 8044 KB Output is correct
3 Correct 260 ms 18264 KB Output is correct
4 Correct 307 ms 18084 KB Output is correct
5 Correct 352 ms 19232 KB Output is correct
6 Correct 528 ms 18880 KB Output is correct
7 Correct 509 ms 19168 KB Output is correct
8 Correct 332 ms 19348 KB Output is correct
9 Correct 237 ms 13812 KB Output is correct
10 Correct 417 ms 13804 KB Output is correct
11 Correct 233 ms 13600 KB Output is correct
12 Correct 340 ms 17284 KB Output is correct
13 Correct 335 ms 18608 KB Output is correct
14 Correct 358 ms 19516 KB Output is correct
15 Correct 336 ms 19440 KB Output is correct
16 Correct 451 ms 15672 KB Output is correct
17 Correct 367 ms 16992 KB Output is correct
18 Correct 238 ms 16764 KB Output is correct
19 Correct 240 ms 17392 KB Output is correct
20 Correct 236 ms 16112 KB Output is correct
21 Correct 347 ms 20000 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8000 KB Output is correct
2 Correct 38 ms 7988 KB Output is correct
3 Correct 279 ms 17668 KB Output is correct
4 Correct 304 ms 18304 KB Output is correct
5 Correct 315 ms 17856 KB Output is correct
6 Correct 347 ms 19492 KB Output is correct
7 Correct 436 ms 17952 KB Output is correct
8 Correct 433 ms 18568 KB Output is correct
9 Correct 285 ms 18796 KB Output is correct
10 Correct 352 ms 19644 KB Output is correct
11 Correct 349 ms 18936 KB Output is correct
12 Correct 322 ms 19652 KB Output is correct
13 Correct 244 ms 14340 KB Output is correct
14 Correct 255 ms 15160 KB Output is correct
15 Correct 255 ms 14436 KB Output is correct
16 Correct 235 ms 14592 KB Output is correct
17 Correct 319 ms 13524 KB Output is correct
18 Correct 274 ms 14244 KB Output is correct
19 Correct 319 ms 17680 KB Output is correct
20 Correct 323 ms 18508 KB Output is correct
21 Correct 354 ms 19092 KB Output is correct
22 Correct 340 ms 18928 KB Output is correct
23 Correct 355 ms 19744 KB Output is correct
24 Correct 329 ms 19572 KB Output is correct
25 Correct 325 ms 17564 KB Output is correct
26 Correct 350 ms 19840 KB Output is correct
27 Correct 276 ms 16320 KB Output is correct
28 Correct 207 ms 16196 KB Output is correct
29 Correct 242 ms 16056 KB Output is correct
30 Correct 328 ms 15628 KB Output is correct
31 Correct 237 ms 16488 KB Output is correct
32 Correct 247 ms 15768 KB Output is correct
33 Correct 380 ms 16756 KB Output is correct
34 Correct 328 ms 17344 KB Output is correct
35 Correct 254 ms 17444 KB Output is correct
36 Correct 373 ms 16232 KB Output is correct
37 Correct 239 ms 16152 KB Output is correct
38 Correct 258 ms 16060 KB Output is correct
39 Correct 318 ms 19884 KB Output is correct
40 Correct 335 ms 20264 KB Output is correct
41 Correct 331 ms 19928 KB Output is correct
42 Correct 371 ms 19932 KB Output is correct