oj.uz

Submission #97164

# Submission time Handle Problem Language Result Execution time Memory
97164 2019-02-14T08:14:09 Z youngyojun Highway Tolls (IOI18_highway) C++11
100 / 100
 487 ms 26320 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef long long ll;

const int MAXN = 90055;
const int MAXM = 130055;

vector<int> G[MAXN], BEV;

vector<int> PEV[2][MAXN], O[2];
int C[2][MAXN], D[2][MAXN];
int A[MAXM], B[MAXM];

int ud[MAXN];

int N, M, CA, CB, L, W, AS, AT;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

void getW() {
	int s = 0, e = M-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V(M, 0);
		fill(V.begin(), V.begin()+m+1, 1);
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	W = s;
}

void calC() {
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	for(int t : {0, 1}) {
		queue<int> PQ;
		C[t][(t ? B : A)[W]] = 1;
		PQ.push((t ? B : A)[W]);
		for(int i, d; !PQ.empty(); PQ.pop()) {
			i = PQ.front();
			d = C[t][i] + 1;
			for(int e : G[i]) {
				int v = A[e] + B[e] - i;
				if(C[t][v]) continue;
				C[t][v] = d;
				PQ.push(v);
			}
		}
	}
}

void dfs(int D[], vector<int> PEV[], int i) {
	for(int e : G[i]) {
		int v = A[e] + B[e] - i;
		PEV[v].eb(e);
		if(D[v]) continue;
		D[v] = D[i] + 1;
		dfs(D, PEV, v);
	}
}

void findS() {
	int s = 0, e = sz(O[0])-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V = BEV;
		for(int i = 0; i <= m; i++)
			V[PEV[0][O[0][i]][0]] = 1;
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	AS = O[0][s];
}

void findT() {
	vector<int> HV;
	int dep = L-D[0][AS]+1;
	for(int i = 0; i < N; i++) if(dep == D[1][i]) HV.eb(i);
	int s = 0, e = sz(HV)-1; for(int m; s < e;) {
		m = (s+e) >> 1;
		vector<int> V = BEV;
		for(int i = 0; i <= m; i++)
			V[PEV[1][HV[i]][0]] = 1;
		if(ll(L)*CA < ask(V)) e = m;
		else s = m+1;
	}
	AT = HV[s];
}

void solve() {
	L = ask(vector<int>(M, 0)) / CA;
	getW();
	calC();
	for(int i = 0; i < N; i++) G[i].clear();
	for(int i = 0, a, b; i < M; i++) {
		a = A[i]; b = B[i];
		if(C[0][a] == C[0][b] || C[1][a] == C[1][b]
			|| C[0][a] == C[1][a] || C[0][b] == C[1][b]
			|| (C[0][a] < C[0][b]) != (C[1][a] < C[1][b])) {
			BEV.eb(1);
			continue;
		}
		BEV.eb(0);
		if(C[0][a] < C[0][b]) G[a].eb(i);
		else G[b].eb(i);
	}
	BEV[W] = 0;
	for(int t : {0, 1}) {
		int v = (t ? B : A)[W];
		D[t][v] = 1; PEV[t][v].eb(W);
		dfs(D[t], PEV[t], v);
		for(int i = 0; i < N; i++)
			if(D[t][i]) O[t].eb(i);
		sort(allv(O[t]), [&](int a, int b) {
			return D[t][a] > D[t][b];
		});
		iota(ud, ud+N, 0);
		for(int v : O[t]) {
			auto &V = PEV[t][v];
			int pe = -1;
			for(int e : V) {
				int p = A[e] + B[e] - v;
				if(uf(p) == uf(v)) continue;
				uf(p, v);
				pe = e;
				break;
			}
			for(int e : V) if(e != pe) BEV[e] = 1;
			V.clear(); V.eb(pe);
		}
	}
	findS();
	findT();
	answer(AS, AT);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::N = N; ::M = U.size(); ::CA = A; ::CB = B;
	for(int i = 0; i < ::M; i++) {
		::A[i] = U[i];
		::B[i] = V[i];
	}
	solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6696 KB Output is correct
2 Correct 35 ms 7800 KB Output is correct
3 Correct 349 ms 17352 KB Output is correct
4 Correct 264 ms 17528 KB Output is correct
5 Correct 254 ms 17516 KB Output is correct
6 Correct 237 ms 17180 KB Output is correct
7 Correct 252 ms 17608 KB Output is correct
8 Correct 259 ms 17528 KB Output is correct
9 Correct 430 ms 17260 KB Output is correct
10 Correct 249 ms 17520 KB Output is correct
11 Correct 369 ms 19420 KB Output is correct
12 Correct 388 ms 20592 KB Output is correct
13 Correct 273 ms 19852 KB Output is correct
14 Correct 396 ms 19872 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8824 KB Output is correct
2 Correct 46 ms 10824 KB Output is correct
3 Correct 79 ms 13024 KB Output is correct
4 Correct 195 ms 23364 KB Output is correct
5 Correct 185 ms 23356 KB Output is correct
6 Correct 211 ms 24904 KB Output is correct
7 Correct 213 ms 26320 KB Output is correct
8 Correct 170 ms 24144 KB Output is correct
9 Correct 185 ms 24480 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6904 KB Output is correct
2 Correct 39 ms 7852 KB Output is correct
3 Correct 195 ms 14988 KB Output is correct
4 Correct 254 ms 17220 KB Output is correct
5 Correct 454 ms 17308 KB Output is correct
6 Correct 263 ms 17224 KB Output is correct
7 Correct 436 ms 17200 KB Output is correct
8 Correct 421 ms 17356 KB Output is correct
9 Correct 384 ms 17512 KB Output is correct
10 Correct 426 ms 17452 KB Output is correct
11 Correct 397 ms 19408 KB Output is correct
12 Correct 267 ms 20708 KB Output is correct
13 Correct 369 ms 20176 KB Output is correct
14 Correct 405 ms 20116 KB Output is correct
15 Correct 282 ms 17080 KB Output is correct
16 Correct 248 ms 17132 KB Output is correct
17 Correct 355 ms 19488 KB Output is correct
18 Correct 426 ms 20172 KB Output is correct
19 Correct 435 ms 17184 KB Output is correct
20 Correct 292 ms 21216 KB Output is correct
21 Correct 283 ms 17928 KB Output is correct
22 Correct 249 ms 17436 KB Output is correct
23 Correct 342 ms 18240 KB Output is correct
24 Correct 316 ms 18784 KB Output is correct
25 Correct 302 ms 25808 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7876 KB Output is correct
2 Correct 56 ms 8092 KB Output is correct
3 Correct 267 ms 17740 KB Output is correct
4 Correct 350 ms 17708 KB Output is correct
5 Correct 375 ms 18484 KB Output is correct
6 Correct 383 ms 18500 KB Output is correct
7 Correct 335 ms 18268 KB Output is correct
8 Correct 310 ms 18240 KB Output is correct
9 Correct 248 ms 14096 KB Output is correct
10 Correct 238 ms 14088 KB Output is correct
11 Correct 269 ms 15292 KB Output is correct
12 Correct 315 ms 16652 KB Output is correct
13 Correct 385 ms 17472 KB Output is correct
14 Correct 399 ms 18268 KB Output is correct
15 Correct 487 ms 18256 KB Output is correct
16 Correct 271 ms 14644 KB Output is correct
17 Correct 347 ms 17852 KB Output is correct
18 Correct 329 ms 18272 KB Output is correct
19 Correct 268 ms 17808 KB Output is correct
20 Correct 401 ms 18320 KB Output is correct
21 Correct 402 ms 19360 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7904 KB Output is correct
2 Correct 22 ms 7900 KB Output is correct
3 Correct 329 ms 17540 KB Output is correct
4 Correct 309 ms 17648 KB Output is correct
5 Correct 331 ms 17952 KB Output is correct
6 Correct 369 ms 18092 KB Output is correct
7 Correct 279 ms 17576 KB Output is correct
8 Correct 295 ms 17812 KB Output is correct
9 Correct 383 ms 17524 KB Output is correct
10 Correct 362 ms 18312 KB Output is correct
11 Correct 382 ms 18312 KB Output is correct
12 Correct 404 ms 18156 KB Output is correct
13 Correct 255 ms 15120 KB Output is correct
14 Correct 274 ms 14116 KB Output is correct
15 Correct 261 ms 15028 KB Output is correct
16 Correct 309 ms 14140 KB Output is correct
17 Correct 299 ms 15468 KB Output is correct
18 Correct 276 ms 14320 KB Output is correct
19 Correct 348 ms 16560 KB Output is correct
20 Correct 449 ms 17568 KB Output is correct
21 Correct 410 ms 18328 KB Output is correct
22 Correct 399 ms 18240 KB Output is correct
23 Correct 419 ms 18252 KB Output is correct
24 Correct 372 ms 18336 KB Output is correct
25 Correct 455 ms 18296 KB Output is correct
26 Correct 430 ms 18256 KB Output is correct
27 Correct 306 ms 17912 KB Output is correct
28 Correct 268 ms 18252 KB Output is correct
29 Correct 344 ms 17700 KB Output is correct
30 Correct 287 ms 17596 KB Output is correct
31 Correct 353 ms 17812 KB Output is correct
32 Correct 282 ms 17708 KB Output is correct
33 Correct 261 ms 18344 KB Output is correct
34 Correct 207 ms 17828 KB Output is correct
35 Correct 315 ms 17776 KB Output is correct
36 Correct 280 ms 18216 KB Output is correct
37 Correct 292 ms 18092 KB Output is correct
38 Correct 328 ms 18112 KB Output is correct
39 Correct 372 ms 19944 KB Output is correct
40 Correct 482 ms 20400 KB Output is correct
41 Correct 362 ms 18856 KB Output is correct
42 Correct 468 ms 19360 KB Output is correct