oj.uz

Submission #567758

# Submission time Handle Problem Language Result Execution time Memory
567758 2022-05-24T07:11:05 Z hhhhaura Swapping Cities (APIO20_swap) C++14
100 / 100
 403 ms 39180 KB 
#define wiwihorz
#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ll long long int
#define pii pair<int, int>
#define INF 2000000000
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
int lg, n, ii, m;
vector<int> dep, par, rk, yes, ord, id, tag, deg;
vector<vector<int>> ac, mp;
int pos(int x) {
	if(par[par[x]] == par[x]) return par[x];
	else return par[x] = pos(par[x]);
}
void unite(int a, int b, int c) {
	int aa = pos(a), bb = pos(b);
	if(aa == bb) return;
	if(rk[aa] < rk[bb]) swap(aa, bb);
	rk[aa] += (rk[aa] == rk[bb]);
	par[bb] = aa;
	yes[aa] |= yes[bb];
	id[aa] = c;
}
void build() {
	ii = n - 1;
	lg = 31 - __builtin_clz(n * 2);
	mp.assign(n * 2, vector<int>());
	ac.assign(lg + 1, vector<int>(n * 2, 0));
	dep.assign(n * 2, 0);
	id.assign(n, 0), iota(all(id), 0);
	par.assign(n, 0), iota(all(par), 0);
	rk.assign(n, 0);
	yes.assign(n, 0);
	ord.assign(m, 0), iota(all(ord), 0);
	tag.assign(n * 2, -1);
	deg.assign(n, 0);
}
void dfs(int x, int par, int d) {
	dep[x] = d;
	ac[0][x] = par;
	for(auto i : mp[x]) if(i != par) {
		dfs(i, x, d + 1);
	}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	build();
	sort(all(ord), [&](int a, int b) {
		return W[a] < W[b];
	});
	for(auto i : ord) {
		int a = U[i], b = V[i], c = W[i];
		deg[a] ++;
		deg[b] ++;
		if(pos(a) == pos(b)) {	
			a = pos(a);
			if(!yes[a]) {
				yes[a] = 1;
				tag[id[a]] = c;
			}
		}
		else {
			mp[++ii].push_back(id[pos(a)]);
			mp[ii].push_back(id[pos(b)]);
			unite(a, b, ii);
			if(deg[a] > 2 || deg[b] > 2) yes[pos(a)] = 1;
			if(yes[pos(a)]) tag[ii] = c;
		}
	}
	dfs(ii, ii, 0);
	rep(i, 1, lg) rep(j, 0, ii) {
		ac[i][j] = ac[i - 1][ac[i - 1][j]];
	}
}
int LCA(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	int need = dep[a] - dep[b];
	rep(i, 0, lg) if((need >> i) & 1) {
		a = ac[i][a];
	} 
	if(a == b) return a;
	rrep(i, 0, lg) if(ac[i][a] != ac[i][b]) {
		a = ac[i][a];
		b = ac[i][b];
	}
	return ac[0][a];
}
int getMinimumFuelCapacity(int X, int Y) {	
	int lca = LCA(X, Y);
	if(tag[lca] != -1) return tag[lca];
	rrep(i, 0, lg) {
		int to = ac[i][lca];
		if(tag[to] == -1) lca = to;
	}
	return tag[ac[0][lca]];
}

Compilation message

swap.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    6 | #pragma loop-opt(on)
      | 
swap.cpp:16:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
swap.cpp:16:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 74 ms 23708 KB Output is correct
10 Correct 104 ms 28764 KB Output is correct
11 Correct 95 ms 28376 KB Output is correct
12 Correct 113 ms 30096 KB Output is correct
13 Correct 98 ms 31500 KB Output is correct
14 Correct 95 ms 23792 KB Output is correct
15 Correct 269 ms 31852 KB Output is correct
16 Correct 285 ms 31216 KB Output is correct
17 Correct 296 ms 32828 KB Output is correct
18 Correct 352 ms 34216 KB Output is correct
19 Correct 107 ms 9756 KB Output is correct
20 Correct 289 ms 34336 KB Output is correct
21 Correct 275 ms 33336 KB Output is correct
22 Correct 276 ms 35288 KB Output is correct
23 Correct 403 ms 36680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 328 ms 35168 KB Output is correct
4 Correct 301 ms 36068 KB Output is correct
5 Correct 338 ms 35304 KB Output is correct
6 Correct 336 ms 35956 KB Output is correct
7 Correct 312 ms 35656 KB Output is correct
8 Correct 324 ms 34376 KB Output is correct
9 Correct 312 ms 35488 KB Output is correct
10 Correct 335 ms 34152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 1 ms 440 KB Output is correct
14 Correct 1 ms 436 KB Output is correct
15 Correct 1 ms 444 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 444 KB Output is correct
22 Correct 2 ms 308 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 480 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 564 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 74 ms 23708 KB Output is correct
11 Correct 104 ms 28764 KB Output is correct
12 Correct 95 ms 28376 KB Output is correct
13 Correct 113 ms 30096 KB Output is correct
14 Correct 98 ms 31500 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 440 KB Output is correct
18 Correct 1 ms 440 KB Output is correct
19 Correct 1 ms 436 KB Output is correct
20 Correct 1 ms 444 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 444 KB Output is correct
27 Correct 2 ms 308 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 480 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 2 ms 564 KB Output is correct
34 Correct 10 ms 4052 KB Output is correct
35 Correct 92 ms 30356 KB Output is correct
36 Correct 90 ms 30288 KB Output is correct
37 Correct 87 ms 30280 KB Output is correct
38 Correct 88 ms 29988 KB Output is correct
39 Correct 84 ms 29756 KB Output is correct
40 Correct 77 ms 27276 KB Output is correct
41 Correct 87 ms 30524 KB Output is correct
42 Correct 83 ms 30252 KB Output is correct
43 Correct 75 ms 32168 KB Output is correct
44 Correct 87 ms 30656 KB Output is correct
45 Correct 97 ms 28020 KB Output is correct
46 Correct 83 ms 30240 KB Output is correct
47 Correct 85 ms 30252 KB Output is correct
48 Correct 87 ms 30812 KB Output is correct
49 Correct 67 ms 7520 KB Output is correct
50 Correct 54 ms 7576 KB Output is correct
51 Correct 84 ms 22800 KB Output is correct
52 Correct 125 ms 33528 KB Output is correct
53 Correct 125 ms 34796 KB Output is correct
54 Correct 134 ms 35264 KB Output is correct
55 Correct 77 ms 31964 KB Output is correct
56 Correct 122 ms 34876 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 74 ms 23708 KB Output is correct
10 Correct 104 ms 28764 KB Output is correct
11 Correct 95 ms 28376 KB Output is correct
12 Correct 113 ms 30096 KB Output is correct
13 Correct 98 ms 31500 KB Output is correct
14 Correct 95 ms 23792 KB Output is correct
15 Correct 269 ms 31852 KB Output is correct
16 Correct 285 ms 31216 KB Output is correct
17 Correct 296 ms 32828 KB Output is correct
18 Correct 352 ms 34216 KB Output is correct
19 Correct 328 ms 35168 KB Output is correct
20 Correct 301 ms 36068 KB Output is correct
21 Correct 338 ms 35304 KB Output is correct
22 Correct 336 ms 35956 KB Output is correct
23 Correct 312 ms 35656 KB Output is correct
24 Correct 324 ms 34376 KB Output is correct
25 Correct 312 ms 35488 KB Output is correct
26 Correct 335 ms 34152 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 440 KB Output is correct
30 Correct 1 ms 440 KB Output is correct
31 Correct 1 ms 436 KB Output is correct
32 Correct 1 ms 444 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 10 ms 4052 KB Output is correct
37 Correct 92 ms 30356 KB Output is correct
38 Correct 90 ms 30288 KB Output is correct
39 Correct 87 ms 30280 KB Output is correct
40 Correct 88 ms 29988 KB Output is correct
41 Correct 84 ms 29756 KB Output is correct
42 Correct 77 ms 27276 KB Output is correct
43 Correct 87 ms 30524 KB Output is correct
44 Correct 83 ms 30252 KB Output is correct
45 Correct 75 ms 32168 KB Output is correct
46 Correct 87 ms 30656 KB Output is correct
47 Correct 17 ms 4236 KB Output is correct
48 Correct 220 ms 35108 KB Output is correct
49 Correct 205 ms 35236 KB Output is correct
50 Correct 210 ms 35000 KB Output is correct
51 Correct 208 ms 34848 KB Output is correct
52 Correct 192 ms 33228 KB Output is correct
53 Correct 162 ms 26156 KB Output is correct
54 Correct 233 ms 36132 KB Output is correct
55 Correct 229 ms 35232 KB Output is correct
56 Correct 299 ms 36776 KB Output is correct
57 Correct 223 ms 36072 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 74 ms 23708 KB Output is correct
11 Correct 104 ms 28764 KB Output is correct
12 Correct 95 ms 28376 KB Output is correct
13 Correct 113 ms 30096 KB Output is correct
14 Correct 98 ms 31500 KB Output is correct
15 Correct 95 ms 23792 KB Output is correct
16 Correct 269 ms 31852 KB Output is correct
17 Correct 285 ms 31216 KB Output is correct
18 Correct 296 ms 32828 KB Output is correct
19 Correct 352 ms 34216 KB Output is correct
20 Correct 328 ms 35168 KB Output is correct
21 Correct 301 ms 36068 KB Output is correct
22 Correct 338 ms 35304 KB Output is correct
23 Correct 336 ms 35956 KB Output is correct
24 Correct 312 ms 35656 KB Output is correct
25 Correct 324 ms 34376 KB Output is correct
26 Correct 312 ms 35488 KB Output is correct
27 Correct 335 ms 34152 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 440 KB Output is correct
31 Correct 1 ms 440 KB Output is correct
32 Correct 1 ms 436 KB Output is correct
33 Correct 1 ms 444 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 10 ms 4052 KB Output is correct
38 Correct 92 ms 30356 KB Output is correct
39 Correct 90 ms 30288 KB Output is correct
40 Correct 87 ms 30280 KB Output is correct
41 Correct 88 ms 29988 KB Output is correct
42 Correct 84 ms 29756 KB Output is correct
43 Correct 77 ms 27276 KB Output is correct
44 Correct 87 ms 30524 KB Output is correct
45 Correct 83 ms 30252 KB Output is correct
46 Correct 75 ms 32168 KB Output is correct
47 Correct 87 ms 30656 KB Output is correct
48 Correct 17 ms 4236 KB Output is correct
49 Correct 220 ms 35108 KB Output is correct
50 Correct 205 ms 35236 KB Output is correct
51 Correct 210 ms 35000 KB Output is correct
52 Correct 208 ms 34848 KB Output is correct
53 Correct 192 ms 33228 KB Output is correct
54 Correct 162 ms 26156 KB Output is correct
55 Correct 233 ms 36132 KB Output is correct
56 Correct 229 ms 35232 KB Output is correct
57 Correct 299 ms 36776 KB Output is correct
58 Correct 223 ms 36072 KB Output is correct
59 Correct 107 ms 9756 KB Output is correct
60 Correct 289 ms 34336 KB Output is correct
61 Correct 275 ms 33336 KB Output is correct
62 Correct 276 ms 35288 KB Output is correct
63 Correct 403 ms 36680 KB Output is correct
64 Correct 1 ms 468 KB Output is correct
65 Correct 1 ms 468 KB Output is correct
66 Correct 1 ms 444 KB Output is correct
67 Correct 2 ms 308 KB Output is correct
68 Correct 1 ms 468 KB Output is correct
69 Correct 2 ms 480 KB Output is correct
70 Correct 2 ms 468 KB Output is correct
71 Correct 2 ms 468 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 2 ms 564 KB Output is correct
74 Correct 97 ms 28020 KB Output is correct
75 Correct 83 ms 30240 KB Output is correct
76 Correct 85 ms 30252 KB Output is correct
77 Correct 87 ms 30812 KB Output is correct
78 Correct 67 ms 7520 KB Output is correct
79 Correct 54 ms 7576 KB Output is correct
80 Correct 84 ms 22800 KB Output is correct
81 Correct 125 ms 33528 KB Output is correct
82 Correct 125 ms 34796 KB Output is correct
83 Correct 134 ms 35264 KB Output is correct
84 Correct 77 ms 31964 KB Output is correct
85 Correct 122 ms 34876 KB Output is correct
86 Correct 60 ms 11440 KB Output is correct
87 Correct 200 ms 35236 KB Output is correct
88 Correct 205 ms 35236 KB Output is correct
89 Correct 253 ms 33788 KB Output is correct
90 Correct 150 ms 11976 KB Output is correct
91 Correct 148 ms 14392 KB Output is correct
92 Correct 205 ms 27804 KB Output is correct
93 Correct 247 ms 38224 KB Output is correct
94 Correct 273 ms 39180 KB Output is correct
95 Correct 277 ms 39100 KB Output is correct
96 Correct 251 ms 36776 KB Output is correct
97 Correct 230 ms 38116 KB Output is correct