oj.uz

Submission #409865

# Submission time Handle Problem Language Result Execution time Memory
409865 2021-05-21T17:26:52 Z jhwest2 Swapping Cities (APIO20_swap) C++14
100 / 100
 485 ms 43948 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 1e5 + 10;
const int INF = 1e9 + 10;

int n, m, Deg[M], Cnt[M], Mx[M], Sz[M], Par[M], A[M], Dep[M], P[20][M], B[20][M];
vector<int> V[M];
vector<pint> G[M];
pair<int, pint> E[M << 1];

int Find(int u) {
	return u == Par[u] ? u : Par[u] = Find(Par[u]);
}
bool is_line(int u) {
	int x = Find(u);
	return Mx[x] <= 2 && Cnt[x] == Sz[x] - 1;
}
void Union(int u, int v, int d) {
	if (Find(u) == Find(v)) {
		int x = Find(u);
		Mx[x] = max({ Mx[x], ++Deg[u], ++Deg[v] });
		Cnt[x]++;
		if (!is_line(x)) {
			for (int k : V[x]) A[k] = d; V[x].clear();
		}
		return;
	}
	int x = Find(u), y = Find(v);
	G[x].emplace_back(d, y); G[y].emplace_back(d, x);
	if (V[x].size() < V[y].size()) {
		swap(x, y), swap(u, v);
	}
	Mx[x] = max({ Mx[x], Mx[y], ++Deg[u], ++Deg[v] });
	Cnt[x] += Cnt[y] + 1; Sz[x] += Sz[y];
	for (int k : V[y]) V[x].push_back(k); V[y].clear();
	Par[y] = x;
	if (!is_line(x)) {
		for (int k : V[x]) A[k] = d; V[x].clear();
	}
}
void dfs(int p, int cur) {
	for (auto [d, x] : G[cur]) if (p != x) {
		P[0][x] = cur; Dep[x] = Dep[cur] + 1; B[0][x] = d;
		for (int i = 1; i < 20; i++) {
			P[i][x] = P[i - 1][P[i - 1][x]];
			B[i][x] = max(B[i - 1][x], B[i - 1][P[i - 1][x]]);
		}
		dfs(cur, x);
	}
}
int query(int u, int v) {
	if (Dep[u] < Dep[v]) swap(u, v);
	int ret = 0;
	for (int i = 19; i >= 0; i--) {
		if (Dep[u] - Dep[v] >> i & 1) {
			ret = max(ret, B[i][u]); u = P[i][u];
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (P[i][u] != P[i][v]) {
			ret = max({ ret, B[i][u], B[i][v] });
			u = P[i][u]; v = P[i][v];
		}
	}
	return u == v ? ret : max({ ret, B[0][u], B[0][v] });
}
void init(int N, int M, vector<int> _U, vector<int> _V, vector<int> _W) {
	n = N; m = M;
	for (int i = 0; i < m; i++) {
		E[i] = { _W[i], {_U[i], _V[i]} };
	}
	sort(E, E + m);
	for (int i = 0; i < n; i++) {
		V[i].push_back(i); Par[i] = i; Sz[i] = 1; A[i] = INF;
	}
	for (int i = 0; i < m; i++) {
		auto [u, v] = E[i].vb;
		Union(u, v, E[i].va);
	}
	dfs(0, 0);

}

int getMinimumFuelCapacity(int u, int v) {
	int ret = max({ query(u, v), A[u], A[v] });
	return ret == INF ? -1 : ret;
}

Compilation message

swap.cpp: In function 'void Union(int, int, int)':
swap.cpp:29:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |    ^~~
swap.cpp:29:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |                                 ^
swap.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |  ^~~
swap.cpp:40:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |                                        ^
swap.cpp:43:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |   ^~~
swap.cpp:43:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |                                ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for (auto [d, x] : G[cur]) if (p != x) {
      |            ^
swap.cpp: In function 'int query(int, int)':
swap.cpp:60:14: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   60 |   if (Dep[u] - Dep[v] >> i & 1) {
      |       ~~~~~~~^~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:82:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |   auto [u, v] = E[i].vb;
      |        ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 5 ms 5348 KB Output is correct
9 Correct 150 ms 30368 KB Output is correct
10 Correct 211 ms 36032 KB Output is correct
11 Correct 180 ms 35548 KB Output is correct
12 Correct 206 ms 37160 KB Output is correct
13 Correct 174 ms 33792 KB Output is correct
14 Correct 159 ms 30628 KB Output is correct
15 Correct 350 ms 38284 KB Output is correct
16 Correct 324 ms 37312 KB Output is correct
17 Correct 347 ms 39044 KB Output is correct
18 Correct 292 ms 35496 KB Output is correct
19 Correct 98 ms 13636 KB Output is correct
20 Correct 358 ms 39356 KB Output is correct
21 Correct 323 ms 38492 KB Output is correct
22 Correct 369 ms 40352 KB Output is correct
23 Correct 297 ms 36896 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 419 ms 42172 KB Output is correct
4 Correct 431 ms 43948 KB Output is correct
5 Correct 446 ms 42876 KB Output is correct
6 Correct 422 ms 43764 KB Output is correct
7 Correct 437 ms 43460 KB Output is correct
8 Correct 426 ms 41888 KB Output is correct
9 Correct 415 ms 43148 KB Output is correct
10 Correct 447 ms 41600 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 5 ms 5348 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 5 ms 5452 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 6 ms 5452 KB Output is correct
13 Correct 5 ms 5376 KB Output is correct
14 Correct 5 ms 5324 KB Output is correct
15 Correct 5 ms 5420 KB Output is correct
16 Correct 4 ms 5452 KB Output is correct
17 Correct 4 ms 5452 KB Output is correct
18 Correct 4 ms 5452 KB Output is correct
19 Correct 4 ms 5452 KB Output is correct
20 Correct 5 ms 5452 KB Output is correct
21 Correct 4 ms 5400 KB Output is correct
22 Correct 4 ms 5324 KB Output is correct
23 Correct 5 ms 5324 KB Output is correct
24 Correct 5 ms 5452 KB Output is correct
25 Correct 5 ms 5532 KB Output is correct
26 Correct 5 ms 5452 KB Output is correct
27 Correct 4 ms 5452 KB Output is correct
28 Correct 5 ms 5452 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 5 ms 5348 KB Output is correct
10 Correct 150 ms 30368 KB Output is correct
11 Correct 211 ms 36032 KB Output is correct
12 Correct 180 ms 35548 KB Output is correct
13 Correct 206 ms 37160 KB Output is correct
14 Correct 174 ms 33792 KB Output is correct
15 Correct 5 ms 5452 KB Output is correct
16 Correct 4 ms 5452 KB Output is correct
17 Correct 6 ms 5452 KB Output is correct
18 Correct 5 ms 5376 KB Output is correct
19 Correct 5 ms 5324 KB Output is correct
20 Correct 5 ms 5420 KB Output is correct
21 Correct 4 ms 5452 KB Output is correct
22 Correct 4 ms 5452 KB Output is correct
23 Correct 4 ms 5452 KB Output is correct
24 Correct 4 ms 5452 KB Output is correct
25 Correct 5 ms 5452 KB Output is correct
26 Correct 4 ms 5400 KB Output is correct
27 Correct 4 ms 5324 KB Output is correct
28 Correct 5 ms 5324 KB Output is correct
29 Correct 5 ms 5452 KB Output is correct
30 Correct 5 ms 5532 KB Output is correct
31 Correct 5 ms 5452 KB Output is correct
32 Correct 4 ms 5452 KB Output is correct
33 Correct 5 ms 5452 KB Output is correct
34 Correct 20 ms 9356 KB Output is correct
35 Correct 198 ms 37572 KB Output is correct
36 Correct 195 ms 37084 KB Output is correct
37 Correct 228 ms 36392 KB Output is correct
38 Correct 186 ms 35556 KB Output is correct
39 Correct 194 ms 34908 KB Output is correct
40 Correct 163 ms 32408 KB Output is correct
41 Correct 198 ms 38008 KB Output is correct
42 Correct 194 ms 38224 KB Output is correct
43 Correct 201 ms 39956 KB Output is correct
44 Correct 198 ms 34952 KB Output is correct
45 Correct 185 ms 32784 KB Output is correct
46 Correct 191 ms 37376 KB Output is correct
47 Correct 184 ms 35796 KB Output is correct
48 Correct 204 ms 36396 KB Output is correct
49 Correct 71 ms 12040 KB Output is correct
50 Correct 63 ms 12448 KB Output is correct
51 Correct 155 ms 28300 KB Output is correct
52 Correct 235 ms 39588 KB Output is correct
53 Correct 234 ms 38788 KB Output is correct
54 Correct 254 ms 41652 KB Output is correct
55 Correct 207 ms 41464 KB Output is correct
56 Correct 229 ms 39612 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 5 ms 5348 KB Output is correct
9 Correct 150 ms 30368 KB Output is correct
10 Correct 211 ms 36032 KB Output is correct
11 Correct 180 ms 35548 KB Output is correct
12 Correct 206 ms 37160 KB Output is correct
13 Correct 174 ms 33792 KB Output is correct
14 Correct 159 ms 30628 KB Output is correct
15 Correct 350 ms 38284 KB Output is correct
16 Correct 324 ms 37312 KB Output is correct
17 Correct 347 ms 39044 KB Output is correct
18 Correct 292 ms 35496 KB Output is correct
19 Correct 419 ms 42172 KB Output is correct
20 Correct 431 ms 43948 KB Output is correct
21 Correct 446 ms 42876 KB Output is correct
22 Correct 422 ms 43764 KB Output is correct
23 Correct 437 ms 43460 KB Output is correct
24 Correct 426 ms 41888 KB Output is correct
25 Correct 415 ms 43148 KB Output is correct
26 Correct 447 ms 41600 KB Output is correct
27 Correct 5 ms 5452 KB Output is correct
28 Correct 4 ms 5452 KB Output is correct
29 Correct 6 ms 5452 KB Output is correct
30 Correct 5 ms 5376 KB Output is correct
31 Correct 5 ms 5324 KB Output is correct
32 Correct 5 ms 5420 KB Output is correct
33 Correct 4 ms 5452 KB Output is correct
34 Correct 4 ms 5452 KB Output is correct
35 Correct 4 ms 5452 KB Output is correct
36 Correct 20 ms 9356 KB Output is correct
37 Correct 198 ms 37572 KB Output is correct
38 Correct 195 ms 37084 KB Output is correct
39 Correct 228 ms 36392 KB Output is correct
40 Correct 186 ms 35556 KB Output is correct
41 Correct 194 ms 34908 KB Output is correct
42 Correct 163 ms 32408 KB Output is correct
43 Correct 198 ms 38008 KB Output is correct
44 Correct 194 ms 38224 KB Output is correct
45 Correct 201 ms 39956 KB Output is correct
46 Correct 198 ms 34952 KB Output is correct
47 Correct 27 ms 9548 KB Output is correct
48 Correct 362 ms 40800 KB Output is correct
49 Correct 354 ms 39896 KB Output is correct
50 Correct 357 ms 39060 KB Output is correct
51 Correct 351 ms 38440 KB Output is correct
52 Correct 378 ms 36268 KB Output is correct
53 Correct 269 ms 28864 KB Output is correct
54 Correct 347 ms 41200 KB Output is correct
55 Correct 344 ms 40860 KB Output is correct
56 Correct 447 ms 43320 KB Output is correct
57 Correct 422 ms 38228 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 5 ms 5348 KB Output is correct
10 Correct 150 ms 30368 KB Output is correct
11 Correct 211 ms 36032 KB Output is correct
12 Correct 180 ms 35548 KB Output is correct
13 Correct 206 ms 37160 KB Output is correct
14 Correct 174 ms 33792 KB Output is correct
15 Correct 159 ms 30628 KB Output is correct
16 Correct 350 ms 38284 KB Output is correct
17 Correct 324 ms 37312 KB Output is correct
18 Correct 347 ms 39044 KB Output is correct
19 Correct 292 ms 35496 KB Output is correct
20 Correct 419 ms 42172 KB Output is correct
21 Correct 431 ms 43948 KB Output is correct
22 Correct 446 ms 42876 KB Output is correct
23 Correct 422 ms 43764 KB Output is correct
24 Correct 437 ms 43460 KB Output is correct
25 Correct 426 ms 41888 KB Output is correct
26 Correct 415 ms 43148 KB Output is correct
27 Correct 447 ms 41600 KB Output is correct
28 Correct 5 ms 5452 KB Output is correct
29 Correct 4 ms 5452 KB Output is correct
30 Correct 6 ms 5452 KB Output is correct
31 Correct 5 ms 5376 KB Output is correct
32 Correct 5 ms 5324 KB Output is correct
33 Correct 5 ms 5420 KB Output is correct
34 Correct 4 ms 5452 KB Output is correct
35 Correct 4 ms 5452 KB Output is correct
36 Correct 4 ms 5452 KB Output is correct
37 Correct 20 ms 9356 KB Output is correct
38 Correct 198 ms 37572 KB Output is correct
39 Correct 195 ms 37084 KB Output is correct
40 Correct 228 ms 36392 KB Output is correct
41 Correct 186 ms 35556 KB Output is correct
42 Correct 194 ms 34908 KB Output is correct
43 Correct 163 ms 32408 KB Output is correct
44 Correct 198 ms 38008 KB Output is correct
45 Correct 194 ms 38224 KB Output is correct
46 Correct 201 ms 39956 KB Output is correct
47 Correct 198 ms 34952 KB Output is correct
48 Correct 27 ms 9548 KB Output is correct
49 Correct 362 ms 40800 KB Output is correct
50 Correct 354 ms 39896 KB Output is correct
51 Correct 357 ms 39060 KB Output is correct
52 Correct 351 ms 38440 KB Output is correct
53 Correct 378 ms 36268 KB Output is correct
54 Correct 269 ms 28864 KB Output is correct
55 Correct 347 ms 41200 KB Output is correct
56 Correct 344 ms 40860 KB Output is correct
57 Correct 447 ms 43320 KB Output is correct
58 Correct 422 ms 38228 KB Output is correct
59 Correct 98 ms 13636 KB Output is correct
60 Correct 358 ms 39356 KB Output is correct
61 Correct 323 ms 38492 KB Output is correct
62 Correct 369 ms 40352 KB Output is correct
63 Correct 297 ms 36896 KB Output is correct
64 Correct 4 ms 5452 KB Output is correct
65 Correct 5 ms 5452 KB Output is correct
66 Correct 4 ms 5400 KB Output is correct
67 Correct 4 ms 5324 KB Output is correct
68 Correct 5 ms 5324 KB Output is correct
69 Correct 5 ms 5452 KB Output is correct
70 Correct 5 ms 5532 KB Output is correct
71 Correct 5 ms 5452 KB Output is correct
72 Correct 4 ms 5452 KB Output is correct
73 Correct 5 ms 5452 KB Output is correct
74 Correct 185 ms 32784 KB Output is correct
75 Correct 191 ms 37376 KB Output is correct
76 Correct 184 ms 35796 KB Output is correct
77 Correct 204 ms 36396 KB Output is correct
78 Correct 71 ms 12040 KB Output is correct
79 Correct 63 ms 12448 KB Output is correct
80 Correct 155 ms 28300 KB Output is correct
81 Correct 235 ms 39588 KB Output is correct
82 Correct 234 ms 38788 KB Output is correct
83 Correct 254 ms 41652 KB Output is correct
84 Correct 207 ms 41464 KB Output is correct
85 Correct 229 ms 39612 KB Output is correct
86 Correct 92 ms 16688 KB Output is correct
87 Correct 353 ms 39508 KB Output is correct
88 Correct 354 ms 39144 KB Output is correct
89 Correct 425 ms 37404 KB Output is correct
90 Correct 186 ms 14660 KB Output is correct
91 Correct 200 ms 16968 KB Output is correct
92 Correct 348 ms 30852 KB Output is correct
93 Correct 390 ms 41728 KB Output is correct
94 Correct 427 ms 40780 KB Output is correct
95 Correct 390 ms 43324 KB Output is correct
96 Correct 485 ms 41260 KB Output is correct
97 Correct 463 ms 40532 KB Output is correct