# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
891700 |
2023-12-23T17:05:07 Z |
ind1v |
Sjekira (COCI20_sjekira) |
C++11 |
|
41 ms |
9584 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct dsu {
int lab[N];
int mx[N];
dsu() {
memset(lab, -1, sizeof(lab));
memset(mx, -1, sizeof(mx));
}
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool merge(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return false;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
lab[u] += lab[v];
lab[v] = u;
mx[u] = max(mx[u], mx[v]);
return true;
}
};
int n;
int t[N];
int ord[N];
bool on[N];
vector<int> g[N];
dsu d;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [](int &u, int &v) -> bool {
return t[u] < t[v];
});
long long ans = 0;
for (int i = 1; i <= n; i++) {
d.mx[ord[i]] = t[ord[i]];
for (int j : g[ord[i]]) {
if (on[j]) {
ans += d.mx[d.find(j)];
ans += t[ord[i]];
d.merge(ord[i], j);
}
}
on[ord[i]] = true;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3416 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8532 KB |
Output is correct |
2 |
Correct |
24 ms |
7252 KB |
Output is correct |
3 |
Correct |
22 ms |
7040 KB |
Output is correct |
4 |
Correct |
29 ms |
7592 KB |
Output is correct |
5 |
Correct |
37 ms |
9552 KB |
Output is correct |
6 |
Correct |
28 ms |
9560 KB |
Output is correct |
7 |
Correct |
24 ms |
8736 KB |
Output is correct |
8 |
Correct |
22 ms |
8276 KB |
Output is correct |
9 |
Correct |
14 ms |
6492 KB |
Output is correct |
10 |
Correct |
28 ms |
9584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3416 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3416 KB |
Output is correct |
6 |
Correct |
1 ms |
3420 KB |
Output is correct |
7 |
Correct |
1 ms |
3412 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
3676 KB |
Output is correct |
10 |
Correct |
2 ms |
3648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3416 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3416 KB |
Output is correct |
6 |
Correct |
29 ms |
8532 KB |
Output is correct |
7 |
Correct |
24 ms |
7252 KB |
Output is correct |
8 |
Correct |
22 ms |
7040 KB |
Output is correct |
9 |
Correct |
29 ms |
7592 KB |
Output is correct |
10 |
Correct |
37 ms |
9552 KB |
Output is correct |
11 |
Correct |
28 ms |
9560 KB |
Output is correct |
12 |
Correct |
24 ms |
8736 KB |
Output is correct |
13 |
Correct |
22 ms |
8276 KB |
Output is correct |
14 |
Correct |
14 ms |
6492 KB |
Output is correct |
15 |
Correct |
28 ms |
9584 KB |
Output is correct |
16 |
Correct |
1 ms |
3420 KB |
Output is correct |
17 |
Correct |
1 ms |
3412 KB |
Output is correct |
18 |
Correct |
1 ms |
3420 KB |
Output is correct |
19 |
Correct |
1 ms |
3676 KB |
Output is correct |
20 |
Correct |
2 ms |
3648 KB |
Output is correct |
21 |
Correct |
9 ms |
4956 KB |
Output is correct |
22 |
Correct |
8 ms |
4700 KB |
Output is correct |
23 |
Correct |
37 ms |
9548 KB |
Output is correct |
24 |
Correct |
26 ms |
7772 KB |
Output is correct |
25 |
Correct |
26 ms |
7656 KB |
Output is correct |
26 |
Correct |
17 ms |
6224 KB |
Output is correct |
27 |
Correct |
20 ms |
6748 KB |
Output is correct |
28 |
Correct |
27 ms |
7516 KB |
Output is correct |
29 |
Correct |
18 ms |
6164 KB |
Output is correct |
30 |
Correct |
41 ms |
9556 KB |
Output is correct |