# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
328087 | 2020-11-15T11:00:19 Z | model_code | Sjekira (COCI20_sjekira) | C++17 | 64 ms | 3936 KB |
#include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAXN = 100005; typedef pair<int,int> ii; int n; int t[MAXN]; vector<ii> e; int uf[MAXN], mv[MAXN]; bool cmp(const ii& a, const ii& b) { int x = max(t[a.first], t[a.second]); int y = max(t[b.first], t[b.second]); return x<y; } int fnd(int x){ if(x==uf[x]) return x; else return uf[x]=fnd(uf[x]); } long long sol = 0; void un(int x, int y){ x = fnd(x); y = fnd(y); if(x != y){ sol += mv[x] + mv[y]; mv[y] = max(mv[y], mv[x]); uf[x] = y; } } int main(){ scanf("%d", &n); for(int i=0;i<n;i++){ scanf("%d", &t[i]); uf[i] = i; mv[i] = t[i]; } for(int i=1;i<n;i++){ int u,v; scanf("%d%d", &u, &v); e.push_back(ii(u-1, v-1)); } sort(e.begin(), e.end(), cmp); for(auto i:e){ un(i.first, i.second); } printf("%lld\n", sol); }
Compilation message
# | 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 0 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 2404 KB | Output is correct |
2 | Correct | 36 ms | 1640 KB | Output is correct |
3 | Correct | 37 ms | 1640 KB | Output is correct |
4 | Correct | 37 ms | 2276 KB | Output is correct |
5 | Correct | 57 ms | 2660 KB | Output is correct |
6 | Correct | 64 ms | 3936 KB | Output is correct |
7 | Correct | 53 ms | 3040 KB | Output is correct |
8 | Correct | 48 ms | 3040 KB | Output is correct |
9 | Correct | 31 ms | 2276 KB | Output is correct |
10 | Correct | 56 ms | 3552 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 0 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 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 | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 0 ms | 364 KB | Output is correct |
6 | Correct | 48 ms | 2404 KB | Output is correct |
7 | Correct | 36 ms | 1640 KB | Output is correct |
8 | Correct | 37 ms | 1640 KB | Output is correct |
9 | Correct | 37 ms | 2276 KB | Output is correct |
10 | Correct | 57 ms | 2660 KB | Output is correct |
11 | Correct | 64 ms | 3936 KB | Output is correct |
12 | Correct | 53 ms | 3040 KB | Output is correct |
13 | Correct | 48 ms | 3040 KB | Output is correct |
14 | Correct | 31 ms | 2276 KB | Output is correct |
15 | Correct | 56 ms | 3552 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 13 ms | 1004 KB | Output is correct |
22 | Correct | 11 ms | 876 KB | Output is correct |
23 | Correct | 60 ms | 2616 KB | Output is correct |
24 | Correct | 41 ms | 2276 KB | Output is correct |
25 | Correct | 40 ms | 2276 KB | Output is correct |
26 | Correct | 26 ms | 1512 KB | Output is correct |
27 | Correct | 32 ms | 1512 KB | Output is correct |
28 | Correct | 46 ms | 2276 KB | Output is correct |
29 | Correct | 27 ms | 1512 KB | Output is correct |
30 | Correct | 62 ms | 2660 KB | Output is correct |