oj.uz

Submission #74973

# Submission time Handle Problem Language Result Execution time Memory
74973 2018-09-07T18:59:05 Z khsoo01 Highway Tolls (IOI18_highway) C++11
90 / 100
 530 ms 21484 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<5;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 8 ms 6648 KB Output is correct
2 Correct 8 ms 6752 KB Output is correct
3 Correct 9 ms 6680 KB Output is correct
4 Correct 8 ms 6676 KB Output is correct
5 Correct 9 ms 6696 KB Output is correct
6 Correct 8 ms 6696 KB Output is correct
7 Correct 8 ms 6884 KB Output is correct
8 Correct 8 ms 6616 KB Output is correct
9 Correct 8 ms 6676 KB Output is correct
10 Correct 8 ms 6688 KB Output is correct
11 Correct 8 ms 6692 KB Output is correct
12 Correct 9 ms 6676 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 36 ms 7964 KB Output is correct
3 Correct 281 ms 17996 KB Output is correct
4 Correct 363 ms 18052 KB Output is correct
5 Correct 293 ms 17988 KB Output is correct
6 Correct 248 ms 18056 KB Output is correct
7 Correct 305 ms 18060 KB Output is correct
8 Correct 318 ms 18056 KB Output is correct
9 Correct 235 ms 18040 KB Output is correct
10 Correct 226 ms 18048 KB Output is correct
11 Correct 403 ms 19316 KB Output is correct
12 Correct 284 ms 19616 KB Output is correct
13 Correct 271 ms 19312 KB Output is correct
14 Correct 258 ms 19180 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8232 KB Output is correct
2 Correct 42 ms 9672 KB Output is correct
3 Correct 56 ms 9148 KB Output is correct
4 Correct 292 ms 18128 KB Output is correct
5 Correct 258 ms 18228 KB Output is correct
6 Correct 141 ms 19712 KB Output is correct
7 Correct 163 ms 14144 KB Output is correct
8 Correct 314 ms 18872 KB Output is correct
9 Correct 160 ms 15112 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 37 ms 7960 KB Output is correct
3 Correct 184 ms 14280 KB Output is correct
4 Correct 241 ms 15100 KB Output is correct
5 Correct 367 ms 16724 KB Output is correct
6 Correct 204 ms 14080 KB Output is correct
7 Correct 228 ms 15596 KB Output is correct
8 Correct 205 ms 15056 KB Output is correct
9 Correct 242 ms 17280 KB Output is correct
10 Correct 273 ms 17816 KB Output is correct
11 Correct 205 ms 15196 KB Output is correct
12 Correct 226 ms 18256 KB Output is correct
13 Correct 278 ms 18248 KB Output is correct
14 Correct 252 ms 17592 KB Output is correct
15 Correct 250 ms 16872 KB Output is correct
16 Correct 283 ms 14816 KB Output is correct
17 Correct 255 ms 17944 KB Output is correct
18 Correct 198 ms 14876 KB Output is correct
19 Correct 182 ms 14052 KB Output is correct
20 Correct 354 ms 14040 KB Output is correct
21 Correct 264 ms 16312 KB Output is correct
22 Correct 213 ms 15520 KB Output is correct
23 Correct 242 ms 17384 KB Output is correct
24 Correct 386 ms 17840 KB Output is correct
25 Correct 273 ms 21484 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7988 KB Output is correct
2 Correct 33 ms 8052 KB Output is correct
3 Correct 429 ms 18268 KB Output is correct
4 Correct 336 ms 18116 KB Output is correct
5 Correct 344 ms 19244 KB Output is correct
6 Correct 359 ms 18844 KB Output is correct
7 Correct 507 ms 19168 KB Output is correct
8 Correct 336 ms 19368 KB Output is correct
9 Correct 287 ms 13816 KB Output is correct
10 Correct 420 ms 13808 KB Output is correct
11 Correct 227 ms 13592 KB Output is correct
12 Correct 488 ms 17280 KB Output is correct
13 Correct 349 ms 18636 KB Output is correct
14 Correct 530 ms 19436 KB Output is correct
15 Correct 352 ms 19436 KB Output is correct
16 Correct 287 ms 15672 KB Output is correct
17 Correct 227 ms 16944 KB Output is correct
18 Correct 368 ms 16760 KB Output is correct
19 Correct 264 ms 17352 KB Output is correct
20 Correct 243 ms 16068 KB Output is correct
21 Correct 517 ms 20012 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8004 KB Output is correct
2 Correct 49 ms 7980 KB Output is correct
3 Correct 273 ms 17652 KB Output is correct
4 Correct 327 ms 18320 KB Output is correct
5 Correct 312 ms 17908 KB Output is correct
6 Correct 344 ms 19504 KB Output is correct
7 Correct 279 ms 17936 KB Output is correct
8 Correct 310 ms 18596 KB Output is correct
9 Correct 438 ms 18792 KB Output is correct
10 Correct 389 ms 19616 KB Output is correct
11 Correct 340 ms 19032 KB Output is correct
12 Correct 528 ms 19660 KB Output is correct
13 Correct 417 ms 14352 KB Output is correct
14 Correct 242 ms 15168 KB Output is correct
15 Correct 265 ms 14424 KB Output is correct
16 Correct 269 ms 14588 KB Output is correct
17 Correct 250 ms 13520 KB Output is correct
18 Correct 266 ms 14252 KB Output is correct
19 Correct 327 ms 17680 KB Output is correct
20 Correct 334 ms 18456 KB Output is correct
21 Correct 369 ms 19092 KB Output is correct
22 Correct 346 ms 18904 KB Output is correct
23 Correct 361 ms 19724 KB Output is correct
24 Correct 376 ms 19592 KB Output is correct
25 Correct 317 ms 17544 KB Output is correct
26 Correct 363 ms 19844 KB Output is correct
27 Correct 243 ms 16288 KB Output is correct
28 Correct 224 ms 16192 KB Output is correct
29 Correct 237 ms 16056 KB Output is correct
30 Correct 278 ms 15628 KB Output is correct
31 Partially correct 235 ms 16504 KB Output is partially correct
32 Partially correct 249 ms 15816 KB Output is partially correct
33 Correct 236 ms 16752 KB Output is correct
34 Correct 310 ms 17356 KB Output is correct
35 Partially correct 239 ms 17556 KB Output is partially correct
36 Correct 246 ms 16220 KB Output is correct
37 Correct 220 ms 16156 KB Output is correct
38 Correct 272 ms 16056 KB Output is correct
39 Correct 411 ms 19884 KB Output is correct
40 Correct 332 ms 20260 KB Output is correct
41 Correct 339 ms 19940 KB Output is correct
42 Correct 369 ms 19904 KB Output is correct