oj.uz

Submission #406303

# Submission time Handle Problem Language Result Execution time Memory
406303 2021-05-17T10:41:27 Z amunduzbaev Swapping Cities (APIO20_swap) C++14
100 / 100
 569 ms 109168 KB 
#include "swap.h"
#include "bits/stdc++.h"
#ifndef EVAL 
#include "grader.cpp"
#endif 
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int N = 3e5+5;
const int mod = 1e9+7;

int n, m, par[N], d[N], f[N], w[N];
vector<int> edges[N];
int lca[N][30], tin[N], tout[N], t;

int fx(int x) { return (x == par[x] ? x : par[x] = fx(par[x])); }
void merge(int a, int b, int c){
	d[a]++, d[b]++;
	int cnd = (max(d[a], d[b]) >= 3);
	a = fx(a), b = fx(b);
	edges[n].pb(a);
	if(b != a) edges[n].pb(b);
	if(a == b){
		par[a] = par[b] = n;
		par[n] = n, f[n] = 1, w[n] = c;
	} else {
		par[a] = par[b] = n, w[n] = c;
		par[n] = n, f[n] = f[a] | f[b] | cnd;
	} n++;
}

void dfs(int u, int p){
	tin[u] = t++;
	lca[u][0] = p;
	for(int j=1;j<30;j++) lca[u][j] = lca[lca[u][j-1]][j-1];
	for(auto x : edges[u]) dfs(x, u);
	tout[u] = t - 1;
}

void init(int32_t N, int32_t M,
	vector<int32_t> a, vector<int32_t> b, vector<int32_t> c) {
	n = N, m = M;
	vector<array<int, 3>> tt;
	for(int i=0;i<m;i++) tt.pb({c[i], a[i], b[i]});
	sort(tt.begin(), tt.end());
	for(int i=0;i<n;i++) par[i] = i;
	for(auto x : tt) merge(x[1], x[2], x[0]);
	//for(int i=n-1;i>=0;i--){
		//for(auto x : edges[i]) cout<<x<<" "<<i<<"\n";
	//}
	memset(lca, -1, sizeof lca);
	dfs(n-1, n-1);
}

bool up(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int f_lca(int a, int b){
	if(up(b, a)) return b;
	if(up(a, b)) return a;
	for(int i=29;i>=0;i--){
		if(up(lca[a][i], b)) continue;
		a = lca[a][i];
	} return lca[a][0];
}

/*

5 4
0 1 0
1 2 1
2 3 2
3 4 3
5
0 1
1 2
2 3
3 4
0 4

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	int lc = f_lca(x, y);
	if(f[lc]) return w[lc];
	for(int i=29;i>=0;i--){
		if(f[lca[lc][i]]) continue;
		lc = lca[lc][i];
	} 
	if(f[lca[lc][0]]) return w[lca[lc][0]];
	else return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 77752 KB Output is correct
2 Correct 37 ms 77760 KB Output is correct
3 Correct 37 ms 77836 KB Output is correct
4 Correct 39 ms 77844 KB Output is correct
5 Correct 38 ms 77900 KB Output is correct
6 Correct 38 ms 77872 KB Output is correct
7 Correct 39 ms 77916 KB Output is correct
8 Correct 38 ms 77928 KB Output is correct
9 Correct 150 ms 89656 KB Output is correct
10 Correct 178 ms 92340 KB Output is correct
11 Correct 179 ms 92060 KB Output is correct
12 Correct 182 ms 92852 KB Output is correct
13 Correct 207 ms 94444 KB Output is correct
14 Correct 165 ms 89776 KB Output is correct
15 Correct 352 ms 94148 KB Output is correct
16 Correct 347 ms 93744 KB Output is correct
17 Correct 357 ms 94660 KB Output is correct
18 Correct 490 ms 96176 KB Output is correct
19 Correct 174 ms 83432 KB Output is correct
20 Correct 341 ms 93976 KB Output is correct
21 Correct 347 ms 93508 KB Output is correct
22 Correct 362 ms 94516 KB Output is correct
23 Correct 532 ms 96052 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 77752 KB Output is correct
2 Correct 37 ms 77760 KB Output is correct
3 Correct 422 ms 96732 KB Output is correct
4 Correct 431 ms 97600 KB Output is correct
5 Correct 445 ms 97064 KB Output is correct
6 Correct 420 ms 97460 KB Output is correct
7 Correct 440 ms 97236 KB Output is correct
8 Correct 432 ms 96564 KB Output is correct
9 Correct 435 ms 97212 KB Output is correct
10 Correct 431 ms 96440 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 77752 KB Output is correct
2 Correct 37 ms 77760 KB Output is correct
3 Correct 37 ms 77836 KB Output is correct
4 Correct 39 ms 77844 KB Output is correct
5 Correct 38 ms 77900 KB Output is correct
6 Correct 38 ms 77872 KB Output is correct
7 Correct 39 ms 77916 KB Output is correct
8 Correct 38 ms 77928 KB Output is correct
9 Correct 38 ms 77800 KB Output is correct
10 Correct 38 ms 77856 KB Output is correct
11 Correct 37 ms 77948 KB Output is correct
12 Correct 38 ms 77952 KB Output is correct
13 Correct 38 ms 77956 KB Output is correct
14 Correct 38 ms 77876 KB Output is correct
15 Correct 38 ms 77892 KB Output is correct
16 Correct 38 ms 77932 KB Output is correct
17 Correct 38 ms 77892 KB Output is correct
18 Correct 39 ms 77980 KB Output is correct
19 Correct 38 ms 77860 KB Output is correct
20 Correct 37 ms 77932 KB Output is correct
21 Correct 39 ms 77896 KB Output is correct
22 Correct 39 ms 78020 KB Output is correct
23 Correct 38 ms 77936 KB Output is correct
24 Correct 39 ms 78060 KB Output is correct
25 Correct 39 ms 78108 KB Output is correct
26 Correct 39 ms 78116 KB Output is correct
27 Correct 38 ms 77940 KB Output is correct
28 Correct 41 ms 78060 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 77800 KB Output is correct
2 Correct 37 ms 77752 KB Output is correct
3 Correct 37 ms 77760 KB Output is correct
4 Correct 37 ms 77836 KB Output is correct
5 Correct 39 ms 77844 KB Output is correct
6 Correct 38 ms 77900 KB Output is correct
7 Correct 38 ms 77872 KB Output is correct
8 Correct 39 ms 77916 KB Output is correct
9 Correct 38 ms 77928 KB Output is correct
10 Correct 150 ms 89656 KB Output is correct
11 Correct 178 ms 92340 KB Output is correct
12 Correct 179 ms 92060 KB Output is correct
13 Correct 182 ms 92852 KB Output is correct
14 Correct 207 ms 94444 KB Output is correct
15 Correct 38 ms 77856 KB Output is correct
16 Correct 37 ms 77948 KB Output is correct
17 Correct 38 ms 77952 KB Output is correct
18 Correct 38 ms 77956 KB Output is correct
19 Correct 38 ms 77876 KB Output is correct
20 Correct 38 ms 77892 KB Output is correct
21 Correct 38 ms 77932 KB Output is correct
22 Correct 38 ms 77892 KB Output is correct
23 Correct 39 ms 77980 KB Output is correct
24 Correct 38 ms 77860 KB Output is correct
25 Correct 37 ms 77932 KB Output is correct
26 Correct 39 ms 77896 KB Output is correct
27 Correct 39 ms 78020 KB Output is correct
28 Correct 38 ms 77936 KB Output is correct
29 Correct 39 ms 78060 KB Output is correct
30 Correct 39 ms 78108 KB Output is correct
31 Correct 39 ms 78116 KB Output is correct
32 Correct 38 ms 77940 KB Output is correct
33 Correct 41 ms 78060 KB Output is correct
34 Correct 53 ms 79824 KB Output is correct
35 Correct 182 ms 92856 KB Output is correct
36 Correct 182 ms 92800 KB Output is correct
37 Correct 183 ms 92780 KB Output is correct
38 Correct 188 ms 92556 KB Output is correct
39 Correct 180 ms 92492 KB Output is correct
40 Correct 169 ms 91204 KB Output is correct
41 Correct 187 ms 92724 KB Output is correct
42 Correct 184 ms 92836 KB Output is correct
43 Correct 197 ms 94780 KB Output is correct
44 Correct 188 ms 92852 KB Output is correct
45 Correct 247 ms 100564 KB Output is correct
46 Correct 180 ms 92720 KB Output is correct
47 Correct 189 ms 92868 KB Output is correct
48 Correct 212 ms 95156 KB Output is correct
49 Correct 182 ms 101336 KB Output is correct
50 Correct 157 ms 95928 KB Output is correct
51 Correct 214 ms 97660 KB Output is correct
52 Correct 251 ms 101928 KB Output is correct
53 Correct 290 ms 103884 KB Output is correct
54 Correct 302 ms 107780 KB Output is correct
55 Correct 198 ms 94652 KB Output is correct
56 Correct 291 ms 104360 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 77752 KB Output is correct
2 Correct 37 ms 77760 KB Output is correct
3 Correct 37 ms 77836 KB Output is correct
4 Correct 39 ms 77844 KB Output is correct
5 Correct 38 ms 77900 KB Output is correct
6 Correct 38 ms 77872 KB Output is correct
7 Correct 39 ms 77916 KB Output is correct
8 Correct 38 ms 77928 KB Output is correct
9 Correct 150 ms 89656 KB Output is correct
10 Correct 178 ms 92340 KB Output is correct
11 Correct 179 ms 92060 KB Output is correct
12 Correct 182 ms 92852 KB Output is correct
13 Correct 207 ms 94444 KB Output is correct
14 Correct 165 ms 89776 KB Output is correct
15 Correct 352 ms 94148 KB Output is correct
16 Correct 347 ms 93744 KB Output is correct
17 Correct 357 ms 94660 KB Output is correct
18 Correct 490 ms 96176 KB Output is correct
19 Correct 422 ms 96732 KB Output is correct
20 Correct 431 ms 97600 KB Output is correct
21 Correct 445 ms 97064 KB Output is correct
22 Correct 420 ms 97460 KB Output is correct
23 Correct 440 ms 97236 KB Output is correct
24 Correct 432 ms 96564 KB Output is correct
25 Correct 435 ms 97212 KB Output is correct
26 Correct 431 ms 96440 KB Output is correct
27 Correct 38 ms 77856 KB Output is correct
28 Correct 37 ms 77948 KB Output is correct
29 Correct 38 ms 77952 KB Output is correct
30 Correct 38 ms 77956 KB Output is correct
31 Correct 38 ms 77876 KB Output is correct
32 Correct 38 ms 77892 KB Output is correct
33 Correct 38 ms 77932 KB Output is correct
34 Correct 38 ms 77892 KB Output is correct
35 Correct 39 ms 77980 KB Output is correct
36 Correct 53 ms 79824 KB Output is correct
37 Correct 182 ms 92856 KB Output is correct
38 Correct 182 ms 92800 KB Output is correct
39 Correct 183 ms 92780 KB Output is correct
40 Correct 188 ms 92556 KB Output is correct
41 Correct 180 ms 92492 KB Output is correct
42 Correct 169 ms 91204 KB Output is correct
43 Correct 187 ms 92724 KB Output is correct
44 Correct 184 ms 92836 KB Output is correct
45 Correct 197 ms 94780 KB Output is correct
46 Correct 188 ms 92852 KB Output is correct
47 Correct 69 ms 79776 KB Output is correct
48 Correct 324 ms 94364 KB Output is correct
49 Correct 329 ms 94384 KB Output is correct
50 Correct 322 ms 94292 KB Output is correct
51 Correct 324 ms 94132 KB Output is correct
52 Correct 316 ms 93168 KB Output is correct
53 Correct 288 ms 89664 KB Output is correct
54 Correct 328 ms 94168 KB Output is correct
55 Correct 339 ms 94388 KB Output is correct
56 Correct 444 ms 95924 KB Output is correct
57 Correct 344 ms 94256 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 77800 KB Output is correct
2 Correct 37 ms 77752 KB Output is correct
3 Correct 37 ms 77760 KB Output is correct
4 Correct 37 ms 77836 KB Output is correct
5 Correct 39 ms 77844 KB Output is correct
6 Correct 38 ms 77900 KB Output is correct
7 Correct 38 ms 77872 KB Output is correct
8 Correct 39 ms 77916 KB Output is correct
9 Correct 38 ms 77928 KB Output is correct
10 Correct 150 ms 89656 KB Output is correct
11 Correct 178 ms 92340 KB Output is correct
12 Correct 179 ms 92060 KB Output is correct
13 Correct 182 ms 92852 KB Output is correct
14 Correct 207 ms 94444 KB Output is correct
15 Correct 165 ms 89776 KB Output is correct
16 Correct 352 ms 94148 KB Output is correct
17 Correct 347 ms 93744 KB Output is correct
18 Correct 357 ms 94660 KB Output is correct
19 Correct 490 ms 96176 KB Output is correct
20 Correct 422 ms 96732 KB Output is correct
21 Correct 431 ms 97600 KB Output is correct
22 Correct 445 ms 97064 KB Output is correct
23 Correct 420 ms 97460 KB Output is correct
24 Correct 440 ms 97236 KB Output is correct
25 Correct 432 ms 96564 KB Output is correct
26 Correct 435 ms 97212 KB Output is correct
27 Correct 431 ms 96440 KB Output is correct
28 Correct 38 ms 77856 KB Output is correct
29 Correct 37 ms 77948 KB Output is correct
30 Correct 38 ms 77952 KB Output is correct
31 Correct 38 ms 77956 KB Output is correct
32 Correct 38 ms 77876 KB Output is correct
33 Correct 38 ms 77892 KB Output is correct
34 Correct 38 ms 77932 KB Output is correct
35 Correct 38 ms 77892 KB Output is correct
36 Correct 39 ms 77980 KB Output is correct
37 Correct 53 ms 79824 KB Output is correct
38 Correct 182 ms 92856 KB Output is correct
39 Correct 182 ms 92800 KB Output is correct
40 Correct 183 ms 92780 KB Output is correct
41 Correct 188 ms 92556 KB Output is correct
42 Correct 180 ms 92492 KB Output is correct
43 Correct 169 ms 91204 KB Output is correct
44 Correct 187 ms 92724 KB Output is correct
45 Correct 184 ms 92836 KB Output is correct
46 Correct 197 ms 94780 KB Output is correct
47 Correct 188 ms 92852 KB Output is correct
48 Correct 69 ms 79776 KB Output is correct
49 Correct 324 ms 94364 KB Output is correct
50 Correct 329 ms 94384 KB Output is correct
51 Correct 322 ms 94292 KB Output is correct
52 Correct 324 ms 94132 KB Output is correct
53 Correct 316 ms 93168 KB Output is correct
54 Correct 288 ms 89664 KB Output is correct
55 Correct 328 ms 94168 KB Output is correct
56 Correct 339 ms 94388 KB Output is correct
57 Correct 444 ms 95924 KB Output is correct
58 Correct 344 ms 94256 KB Output is correct
59 Correct 174 ms 83432 KB Output is correct
60 Correct 341 ms 93976 KB Output is correct
61 Correct 347 ms 93508 KB Output is correct
62 Correct 362 ms 94516 KB Output is correct
63 Correct 532 ms 96052 KB Output is correct
64 Correct 38 ms 77860 KB Output is correct
65 Correct 37 ms 77932 KB Output is correct
66 Correct 39 ms 77896 KB Output is correct
67 Correct 39 ms 78020 KB Output is correct
68 Correct 38 ms 77936 KB Output is correct
69 Correct 39 ms 78060 KB Output is correct
70 Correct 39 ms 78108 KB Output is correct
71 Correct 39 ms 78116 KB Output is correct
72 Correct 38 ms 77940 KB Output is correct
73 Correct 41 ms 78060 KB Output is correct
74 Correct 247 ms 100564 KB Output is correct
75 Correct 180 ms 92720 KB Output is correct
76 Correct 189 ms 92868 KB Output is correct
77 Correct 212 ms 95156 KB Output is correct
78 Correct 182 ms 101336 KB Output is correct
79 Correct 157 ms 95928 KB Output is correct
80 Correct 214 ms 97660 KB Output is correct
81 Correct 251 ms 101928 KB Output is correct
82 Correct 290 ms 103884 KB Output is correct
83 Correct 302 ms 107780 KB Output is correct
84 Correct 198 ms 94652 KB Output is correct
85 Correct 291 ms 104360 KB Output is correct
86 Correct 162 ms 85888 KB Output is correct
87 Correct 338 ms 94284 KB Output is correct
88 Correct 329 ms 94156 KB Output is correct
89 Correct 448 ms 96008 KB Output is correct
90 Correct 327 ms 104232 KB Output is correct
91 Correct 364 ms 101544 KB Output is correct
92 Correct 471 ms 98124 KB Output is correct
93 Correct 434 ms 102872 KB Output is correct
94 Correct 569 ms 105176 KB Output is correct
95 Correct 468 ms 109168 KB Output is correct
96 Correct 466 ms 96048 KB Output is correct
97 Correct 508 ms 100316 KB Output is correct