oj.uz

Submission #319954

# Submission time Handle Problem Language Result Execution time Memory
319954 2020-11-06T22:48:43 Z Blagojce Swapping Cities (APIO20_swap) C++11
100 / 100
 743 ms 44464 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 1e5+5;
mt19937 _rand(time(NULL));

#include "swap.h"

vector<pii> g[mxn];
int n, m;
int sparse[mxn][20];
int mxw[mxn][20];

int depth[mxn];

int _c[mxn];
int dp[mxn];
void dfs(int u, int p, int val, int val2){
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	
	mxw[u][0] = val2;
	fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
	
	int mi1 = i_inf, c1 = -1;
	int mi2 = i_inf;
	
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.nd < mi1){
			mi2 = mi1;
			mi1 = e.nd;
			c1 = e.st;
		}
		else if(e.nd < mi2){
			mi2 = e.nd;
		}
	}
	dp[u] = _c[u];
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		if(e.st != c1){
			dfs(e.st, u, mi1, e.nd);
		}
		else{
			dfs(e.st, u, mi2, e.nd);
		}
		dp[u] = min(dp[u], max(dp[e.st], e.nd));
	}
}
int dpup[mxn];
void dfs2(int u, int p, int carry){
	carry = min(carry, _c[u]);
	dpup[u] = carry;
	int id = p;
	int min1 = carry;
	int min2 = i_inf;
	for(auto e : g[u]){
		if(e.st == p) continue;
		int cand1 = max(dp[e.st], e.nd);
		if(cand1 < min1){
			min2 = min1;
			id = e.st;
			min1 = cand1;
		}else if(cand1 < min2){
			min2 = cand1;
		}
	}
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.st == id){
			dfs2(e.st, u, max(e.nd, min2));
		}
		else{
			dfs2(e.st, u, max(e.nd, min1));
		}
	}
}

int lca(int a, int b){
	int mind = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a] - (1<<i) >= mind) a = sparse[a][i];
		if(depth[b] - (1<<i) >= mind) b = sparse[b][i];
	}
	if(a == b) return a;
	
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
int cost(int u, int p){
	int ret = 0;
	for(int i = 19; i >= 0; i --){
		if(depth[u] - (1<<i) >= depth[p]){
			ret = max(ret, mxw[u][i]);
			u = sparse[u][i];
		}
	}
	return ret;
}

int link[mxn];
int sz[mxn];
bool used[200005];
int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}
void unite(int a, int b, int wi, int i){
	int u = a, v = b;
	a = findx(a);
	b = findx(b);
	if(a == b) return; 
	used[i] = true;
	if(sz[a] < sz[b]) swap(a, b);
	link[b] = a;
	sz[a] += sz[b];
	g[u].pb({v, wi});
	g[v].pb({u, wi});
}
vector<pii> G[mxn];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
	n = N, m = M;
	vector<pii> S;
	fr(i, 0, m){
		S.pb({W[i], i});
	}
	sort(all(S));
	fr(i, 0, n){
		link[i] = i;
		sz[i] = 1;
	}
	for(auto edge : S){
		int u = U[edge.nd];
		int v = V[edge.nd];
		unite(u, v, edge.st, edge.nd);
	}
	fr(i, 0, m){
		G[U[i]].pb({W[i], i});
		G[V[i]].pb({W[i], i});
	}
	fr(i, 0, n){
		sort(all(g[i]), [](const pii A, const pii B){
			return A.nd < B.nd;
		});
		sort(all(G[i]));
	}
	fr(i, 0, n){
		_c[i] = i_inf;
		if((int)g[i].size() >= 3) _c[i] = g[i][2].nd;
		for(auto u : G[i]){
			if(used[u.nd]) continue;
			_c[i] = min(_c[i], u.st);
			break;
		}
	}
	dfs(0, 0, i_inf, i_inf);
	dfs2(0, 0, i_inf);
}

int line = 0;
int getMinimumFuelCapacity(int X, int Y){
	int k = lca(X, Y);	
	int c = max(min(dp[k], dpup[k]), max(cost(X, k), cost(Y, k)));
	if(c == i_inf) c = -1;
	return c;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5612 KB Output is correct
9 Correct 186 ms 31192 KB Output is correct
10 Correct 251 ms 38520 KB Output is correct
11 Correct 261 ms 37548 KB Output is correct
12 Correct 259 ms 39568 KB Output is correct
13 Correct 252 ms 41816 KB Output is correct
14 Correct 221 ms 30680 KB Output is correct
15 Correct 585 ms 40024 KB Output is correct
16 Correct 592 ms 37336 KB Output is correct
17 Correct 573 ms 43388 KB Output is correct
18 Correct 571 ms 41688 KB Output is correct
19 Correct 141 ms 14312 KB Output is correct
20 Correct 590 ms 39880 KB Output is correct
21 Correct 585 ms 37940 KB Output is correct
22 Correct 634 ms 41384 KB Output is correct
23 Correct 570 ms 42156 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 288 ms 34836 KB Output is correct
4 Correct 293 ms 36140 KB Output is correct
5 Correct 306 ms 35456 KB Output is correct
6 Correct 289 ms 36016 KB Output is correct
7 Correct 304 ms 36060 KB Output is correct
8 Correct 291 ms 34728 KB Output is correct
9 Correct 308 ms 35552 KB Output is correct
10 Correct 289 ms 34656 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 5 ms 5612 KB Output is correct
10 Correct 6 ms 5504 KB Output is correct
11 Correct 5 ms 5356 KB Output is correct
12 Correct 5 ms 5356 KB Output is correct
13 Correct 4 ms 5356 KB Output is correct
14 Correct 5 ms 5356 KB Output is correct
15 Correct 5 ms 5356 KB Output is correct
16 Correct 5 ms 5356 KB Output is correct
17 Correct 5 ms 5356 KB Output is correct
18 Correct 6 ms 5356 KB Output is correct
19 Correct 4 ms 5356 KB Output is correct
20 Correct 5 ms 5356 KB Output is correct
21 Correct 5 ms 5356 KB Output is correct
22 Correct 5 ms 5228 KB Output is correct
23 Correct 4 ms 5228 KB Output is correct
24 Correct 6 ms 5484 KB Output is correct
25 Correct 5 ms 5356 KB Output is correct
26 Correct 5 ms 5484 KB Output is correct
27 Correct 5 ms 5356 KB Output is correct
28 Correct 5 ms 5356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 5 ms 5612 KB Output is correct
10 Correct 186 ms 31192 KB Output is correct
11 Correct 251 ms 38520 KB Output is correct
12 Correct 261 ms 37548 KB Output is correct
13 Correct 259 ms 39568 KB Output is correct
14 Correct 252 ms 41816 KB Output is correct
15 Correct 6 ms 5504 KB Output is correct
16 Correct 5 ms 5356 KB Output is correct
17 Correct 5 ms 5356 KB Output is correct
18 Correct 4 ms 5356 KB Output is correct
19 Correct 5 ms 5356 KB Output is correct
20 Correct 5 ms 5356 KB Output is correct
21 Correct 5 ms 5356 KB Output is correct
22 Correct 5 ms 5356 KB Output is correct
23 Correct 6 ms 5356 KB Output is correct
24 Correct 22 ms 9068 KB Output is correct
25 Correct 268 ms 39128 KB Output is correct
26 Correct 249 ms 35928 KB Output is correct
27 Correct 238 ms 33752 KB Output is correct
28 Correct 219 ms 32984 KB Output is correct
29 Correct 208 ms 32220 KB Output is correct
30 Correct 185 ms 30280 KB Output is correct
31 Correct 259 ms 36824 KB Output is correct
32 Correct 264 ms 38296 KB Output is correct
33 Correct 243 ms 39768 KB Output is correct
34 Correct 206 ms 33648 KB Output is correct
35 Correct 4 ms 5356 KB Output is correct
36 Correct 5 ms 5356 KB Output is correct
37 Correct 5 ms 5356 KB Output is correct
38 Correct 5 ms 5228 KB Output is correct
39 Correct 4 ms 5228 KB Output is correct
40 Correct 6 ms 5484 KB Output is correct
41 Correct 5 ms 5356 KB Output is correct
42 Correct 5 ms 5484 KB Output is correct
43 Correct 5 ms 5356 KB Output is correct
44 Correct 5 ms 5356 KB Output is correct
45 Correct 209 ms 31572 KB Output is correct
46 Correct 242 ms 34648 KB Output is correct
47 Correct 211 ms 32564 KB Output is correct
48 Correct 209 ms 33240 KB Output is correct
49 Correct 101 ms 15316 KB Output is correct
50 Correct 82 ms 14052 KB Output is correct
51 Correct 164 ms 27096 KB Output is correct
52 Correct 295 ms 38868 KB Output is correct
53 Correct 324 ms 38228 KB Output is correct
54 Correct 339 ms 43220 KB Output is correct
55 Correct 237 ms 41432 KB Output is correct
56 Correct 287 ms 37716 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5612 KB Output is correct
9 Correct 186 ms 31192 KB Output is correct
10 Correct 251 ms 38520 KB Output is correct
11 Correct 261 ms 37548 KB Output is correct
12 Correct 259 ms 39568 KB Output is correct
13 Correct 252 ms 41816 KB Output is correct
14 Correct 221 ms 30680 KB Output is correct
15 Correct 585 ms 40024 KB Output is correct
16 Correct 592 ms 37336 KB Output is correct
17 Correct 573 ms 43388 KB Output is correct
18 Correct 571 ms 41688 KB Output is correct
19 Correct 288 ms 34836 KB Output is correct
20 Correct 293 ms 36140 KB Output is correct
21 Correct 306 ms 35456 KB Output is correct
22 Correct 289 ms 36016 KB Output is correct
23 Correct 304 ms 36060 KB Output is correct
24 Correct 291 ms 34728 KB Output is correct
25 Correct 308 ms 35552 KB Output is correct
26 Correct 289 ms 34656 KB Output is correct
27 Correct 6 ms 5504 KB Output is correct
28 Correct 5 ms 5356 KB Output is correct
29 Correct 5 ms 5356 KB Output is correct
30 Correct 4 ms 5356 KB Output is correct
31 Correct 5 ms 5356 KB Output is correct
32 Correct 5 ms 5356 KB Output is correct
33 Correct 5 ms 5356 KB Output is correct
34 Correct 5 ms 5356 KB Output is correct
35 Correct 6 ms 5356 KB Output is correct
36 Correct 22 ms 9068 KB Output is correct
37 Correct 268 ms 39128 KB Output is correct
38 Correct 249 ms 35928 KB Output is correct
39 Correct 238 ms 33752 KB Output is correct
40 Correct 219 ms 32984 KB Output is correct
41 Correct 208 ms 32220 KB Output is correct
42 Correct 185 ms 30280 KB Output is correct
43 Correct 259 ms 36824 KB Output is correct
44 Correct 264 ms 38296 KB Output is correct
45 Correct 243 ms 39768 KB Output is correct
46 Correct 206 ms 33648 KB Output is correct
47 Correct 33 ms 8840 KB Output is correct
48 Correct 626 ms 38828 KB Output is correct
49 Correct 609 ms 36780 KB Output is correct
50 Correct 583 ms 35680 KB Output is correct
51 Correct 525 ms 35004 KB Output is correct
52 Correct 458 ms 33060 KB Output is correct
53 Correct 347 ms 27200 KB Output is correct
54 Correct 613 ms 38440 KB Output is correct
55 Correct 622 ms 39572 KB Output is correct
56 Correct 572 ms 42584 KB Output is correct
57 Correct 474 ms 36136 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 5 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 5 ms 5612 KB Output is correct
10 Correct 186 ms 31192 KB Output is correct
11 Correct 251 ms 38520 KB Output is correct
12 Correct 261 ms 37548 KB Output is correct
13 Correct 259 ms 39568 KB Output is correct
14 Correct 252 ms 41816 KB Output is correct
15 Correct 221 ms 30680 KB Output is correct
16 Correct 585 ms 40024 KB Output is correct
17 Correct 592 ms 37336 KB Output is correct
18 Correct 573 ms 43388 KB Output is correct
19 Correct 571 ms 41688 KB Output is correct
20 Correct 288 ms 34836 KB Output is correct
21 Correct 293 ms 36140 KB Output is correct
22 Correct 306 ms 35456 KB Output is correct
23 Correct 289 ms 36016 KB Output is correct
24 Correct 304 ms 36060 KB Output is correct
25 Correct 291 ms 34728 KB Output is correct
26 Correct 308 ms 35552 KB Output is correct
27 Correct 289 ms 34656 KB Output is correct
28 Correct 6 ms 5504 KB Output is correct
29 Correct 5 ms 5356 KB Output is correct
30 Correct 5 ms 5356 KB Output is correct
31 Correct 4 ms 5356 KB Output is correct
32 Correct 5 ms 5356 KB Output is correct
33 Correct 5 ms 5356 KB Output is correct
34 Correct 5 ms 5356 KB Output is correct
35 Correct 5 ms 5356 KB Output is correct
36 Correct 6 ms 5356 KB Output is correct
37 Correct 22 ms 9068 KB Output is correct
38 Correct 268 ms 39128 KB Output is correct
39 Correct 249 ms 35928 KB Output is correct
40 Correct 238 ms 33752 KB Output is correct
41 Correct 219 ms 32984 KB Output is correct
42 Correct 208 ms 32220 KB Output is correct
43 Correct 185 ms 30280 KB Output is correct
44 Correct 259 ms 36824 KB Output is correct
45 Correct 264 ms 38296 KB Output is correct
46 Correct 243 ms 39768 KB Output is correct
47 Correct 206 ms 33648 KB Output is correct
48 Correct 33 ms 8840 KB Output is correct
49 Correct 626 ms 38828 KB Output is correct
50 Correct 609 ms 36780 KB Output is correct
51 Correct 583 ms 35680 KB Output is correct
52 Correct 525 ms 35004 KB Output is correct
53 Correct 458 ms 33060 KB Output is correct
54 Correct 347 ms 27200 KB Output is correct
55 Correct 613 ms 38440 KB Output is correct
56 Correct 622 ms 39572 KB Output is correct
57 Correct 572 ms 42584 KB Output is correct
58 Correct 474 ms 36136 KB Output is correct
59 Correct 141 ms 14312 KB Output is correct
60 Correct 590 ms 39880 KB Output is correct
61 Correct 585 ms 37940 KB Output is correct
62 Correct 634 ms 41384 KB Output is correct
63 Correct 570 ms 42156 KB Output is correct
64 Correct 4 ms 5356 KB Output is correct
65 Correct 5 ms 5356 KB Output is correct
66 Correct 5 ms 5356 KB Output is correct
67 Correct 5 ms 5228 KB Output is correct
68 Correct 4 ms 5228 KB Output is correct
69 Correct 6 ms 5484 KB Output is correct
70 Correct 5 ms 5356 KB Output is correct
71 Correct 5 ms 5484 KB Output is correct
72 Correct 5 ms 5356 KB Output is correct
73 Correct 5 ms 5356 KB Output is correct
74 Correct 209 ms 31572 KB Output is correct
75 Correct 242 ms 34648 KB Output is correct
76 Correct 211 ms 32564 KB Output is correct
77 Correct 209 ms 33240 KB Output is correct
78 Correct 101 ms 15316 KB Output is correct
79 Correct 82 ms 14052 KB Output is correct
80 Correct 164 ms 27096 KB Output is correct
81 Correct 295 ms 38868 KB Output is correct
82 Correct 324 ms 38228 KB Output is correct
83 Correct 339 ms 43220 KB Output is correct
84 Correct 237 ms 41432 KB Output is correct
85 Correct 287 ms 37716 KB Output is correct
86 Correct 105 ms 15452 KB Output is correct
87 Correct 594 ms 36268 KB Output is correct
88 Correct 588 ms 36652 KB Output is correct
89 Correct 407 ms 33072 KB Output is correct
90 Correct 227 ms 16468 KB Output is correct
91 Correct 247 ms 17880 KB Output is correct
92 Correct 368 ms 28732 KB Output is correct
93 Correct 662 ms 40916 KB Output is correct
94 Correct 506 ms 39764 KB Output is correct
95 Correct 743 ms 44464 KB Output is correct
96 Correct 581 ms 40104 KB Output is correct
97 Correct 465 ms 37384 KB Output is correct