# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
947152 |
2024-03-15T15:07:10 Z |
NK_ |
Sjekira (COCI20_sjekira) |
C++17 |
|
34 ms |
4820 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using ll = long long;
const int nax = 1e5+5;
int e[nax], mx[nax];
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
void unite(int x, int y) {
x = get(x), y = get(y);
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x; mx[x] = max(mx[x], mx[y]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
for(int i = 0; i < N; i++) {
cin >> mx[i];
e[i] = -1;
}
V<AR<int, 3>> E; for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v; --u, --v;
E.pb({max(mx[u], mx[v]), u, v});
}
sort(begin(E), end(E));
ll ans = 0;
for(auto& [w, u, v] : E) {
ans += mx[get(u)] + mx[get(v)];
unite(u, v);
}
cout << ans << nl;
exit(0-0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4308 KB |
Output is correct |
2 |
Correct |
19 ms |
3028 KB |
Output is correct |
3 |
Correct |
18 ms |
2964 KB |
Output is correct |
4 |
Correct |
20 ms |
4048 KB |
Output is correct |
5 |
Correct |
30 ms |
4596 KB |
Output is correct |
6 |
Correct |
34 ms |
4816 KB |
Output is correct |
7 |
Correct |
26 ms |
4560 KB |
Output is correct |
8 |
Correct |
23 ms |
4304 KB |
Output is correct |
9 |
Correct |
16 ms |
2648 KB |
Output is correct |
10 |
Correct |
28 ms |
4812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
24 ms |
4308 KB |
Output is correct |
7 |
Correct |
19 ms |
3028 KB |
Output is correct |
8 |
Correct |
18 ms |
2964 KB |
Output is correct |
9 |
Correct |
20 ms |
4048 KB |
Output is correct |
10 |
Correct |
30 ms |
4596 KB |
Output is correct |
11 |
Correct |
34 ms |
4816 KB |
Output is correct |
12 |
Correct |
26 ms |
4560 KB |
Output is correct |
13 |
Correct |
23 ms |
4304 KB |
Output is correct |
14 |
Correct |
16 ms |
2648 KB |
Output is correct |
15 |
Correct |
28 ms |
4812 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
7 ms |
1564 KB |
Output is correct |
22 |
Correct |
6 ms |
1348 KB |
Output is correct |
23 |
Correct |
31 ms |
4628 KB |
Output is correct |
24 |
Correct |
21 ms |
4236 KB |
Output is correct |
25 |
Correct |
21 ms |
4052 KB |
Output is correct |
26 |
Correct |
14 ms |
2648 KB |
Output is correct |
27 |
Correct |
18 ms |
2644 KB |
Output is correct |
28 |
Correct |
23 ms |
3800 KB |
Output is correct |
29 |
Correct |
15 ms |
2388 KB |
Output is correct |
30 |
Correct |
31 ms |
4820 KB |
Output is correct |