# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
513119 |
2022-01-17T02:27:24 Z |
KoD |
Sjekira (COCI20_sjekira) |
C++17 |
|
53 ms |
4376 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
struct UnionFind {
vector<int> par;
UnionFind(const int n) : par(n, -1) {}
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
int merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return x;
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
return x;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
vector<int> C(N);
for (auto& x : C) {
std::cin >> x;
}
vector<tuple<int, int, int>> edge(N - 1);
for (auto& [c, x, y] : edge) {
std::cin >> x >> y;
x -= 1, y -= 1;
c = std::max(C[x], C[y]);
}
std::sort(edge.begin(), edge.end());
UnionFind dsu(N);
long long ans = 0;
for (auto& [c, x, y] : edge) {
x = dsu.find(x), y = dsu.find(y);
ans += C[x] + C[y];
const int z = dsu.merge(x, y);
C[z] = std::max(C[x], C[y]);
}
std::cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
3560 KB |
Output is correct |
2 |
Correct |
27 ms |
2756 KB |
Output is correct |
3 |
Correct |
27 ms |
2624 KB |
Output is correct |
4 |
Correct |
26 ms |
2992 KB |
Output is correct |
5 |
Correct |
34 ms |
4292 KB |
Output is correct |
6 |
Correct |
38 ms |
4376 KB |
Output is correct |
7 |
Correct |
32 ms |
3828 KB |
Output is correct |
8 |
Correct |
27 ms |
3448 KB |
Output is correct |
9 |
Correct |
19 ms |
2324 KB |
Output is correct |
10 |
Correct |
37 ms |
4292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
53 ms |
3560 KB |
Output is correct |
7 |
Correct |
27 ms |
2756 KB |
Output is correct |
8 |
Correct |
27 ms |
2624 KB |
Output is correct |
9 |
Correct |
26 ms |
2992 KB |
Output is correct |
10 |
Correct |
34 ms |
4292 KB |
Output is correct |
11 |
Correct |
38 ms |
4376 KB |
Output is correct |
12 |
Correct |
32 ms |
3828 KB |
Output is correct |
13 |
Correct |
27 ms |
3448 KB |
Output is correct |
14 |
Correct |
19 ms |
2324 KB |
Output is correct |
15 |
Correct |
37 ms |
4292 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
324 KB |
Output is correct |
21 |
Correct |
12 ms |
1160 KB |
Output is correct |
22 |
Correct |
7 ms |
1000 KB |
Output is correct |
23 |
Correct |
46 ms |
4044 KB |
Output is correct |
24 |
Correct |
29 ms |
2988 KB |
Output is correct |
25 |
Correct |
26 ms |
3008 KB |
Output is correct |
26 |
Correct |
15 ms |
2004 KB |
Output is correct |
27 |
Correct |
19 ms |
2360 KB |
Output is correct |
28 |
Correct |
28 ms |
2752 KB |
Output is correct |
29 |
Correct |
21 ms |
1996 KB |
Output is correct |
30 |
Correct |
44 ms |
4344 KB |
Output is correct |