# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
328519 |
2020-11-16T21:04:29 Z |
BarSa |
Sjekira (COCI20_sjekira) |
C++17 |
|
79 ms |
13524 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define ii pair<int,int>
#define vii vector<ii>
#define pqi priority_queue<int>
#define all(arr) arr.begin(), arr.end()
#define si stack<int>
#define qi queue<int>
const int INF = 1e18;
vvi g;
vi t;
vii t_sorted;
vi visited;
vii edges;
struct DSU{
vi p;
vi sz;
vi mx;
void init(int n){
p.resize(n);
sz.resize(n);
mx.resize(n);
for(int i=0; i<n; i++){p[i] = i; sz[i] = 1;mx[i] = t[i];}
}
int find(int a){
if(p[a] == a) return a;
return p[a]=find(p[a]);
}
int find_max(int a){
a = find(a);
return mx[a];
}
void uni(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
if(mx[a] < mx[b]) mx[a] = mx[b];
sz[a] += sz[b];
}
}
};
DSU d;
void solve(){
int n; cin >> n;
visited.resize(n, 0);
for(int i=0; i<n; i++){
int a; cin >> a;
t.push_back(a);
t_sorted.push_back({-a, i});
}
sort(all(t_sorted));
g.resize(n);
for(int i=0; i<n-1; i++){
int u, v; cin >> u >> v; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
for(int i=0; i<n; i++){
visited[t_sorted[i].second] = 1;
for(auto nei: g[t_sorted[i].second]){
if(visited[nei]) continue;
edges.push_back({t_sorted[i].second, nei});
}
}
d.init(n);
for(int i=n-2; i>=0; i--){
int a = edges[i].first, b = edges[i].second;
ans += d.find_max(a);
ans += d.find_max(b);
d.uni(a, b);
}
cout << ans << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
int t=1;
//cin >> t;
for(int i=0; i<t; i++) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
10600 KB |
Output is correct |
2 |
Correct |
42 ms |
8164 KB |
Output is correct |
3 |
Correct |
40 ms |
7904 KB |
Output is correct |
4 |
Correct |
49 ms |
9192 KB |
Output is correct |
5 |
Correct |
69 ms |
12904 KB |
Output is correct |
6 |
Correct |
53 ms |
13012 KB |
Output is correct |
7 |
Correct |
47 ms |
11244 KB |
Output is correct |
8 |
Correct |
43 ms |
10196 KB |
Output is correct |
9 |
Correct |
28 ms |
6748 KB |
Output is correct |
10 |
Correct |
59 ms |
12884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
58 ms |
10600 KB |
Output is correct |
7 |
Correct |
42 ms |
8164 KB |
Output is correct |
8 |
Correct |
40 ms |
7904 KB |
Output is correct |
9 |
Correct |
49 ms |
9192 KB |
Output is correct |
10 |
Correct |
69 ms |
12904 KB |
Output is correct |
11 |
Correct |
53 ms |
13012 KB |
Output is correct |
12 |
Correct |
47 ms |
11244 KB |
Output is correct |
13 |
Correct |
43 ms |
10196 KB |
Output is correct |
14 |
Correct |
28 ms |
6748 KB |
Output is correct |
15 |
Correct |
59 ms |
12884 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
20 ms |
3560 KB |
Output is correct |
22 |
Correct |
13 ms |
2936 KB |
Output is correct |
23 |
Correct |
74 ms |
12888 KB |
Output is correct |
24 |
Correct |
54 ms |
9684 KB |
Output is correct |
25 |
Correct |
51 ms |
9556 KB |
Output is correct |
26 |
Correct |
33 ms |
6240 KB |
Output is correct |
27 |
Correct |
37 ms |
7260 KB |
Output is correct |
28 |
Correct |
60 ms |
10196 KB |
Output is correct |
29 |
Correct |
38 ms |
6880 KB |
Output is correct |
30 |
Correct |
79 ms |
13524 KB |
Output is correct |