# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
897470 | 2024-01-03T07:05:16 Z | mihtriii295 | Sjekira (COCI20_sjekira) | C++17 | 39 ms | 5844 KB |
#include<bits/stdc++.h> #pragma GCC optimize("O2") #define ll long long #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define el cout << '\n' using namespace std; const ll N = 1e5 + 1; const ll logN = 20; const ll MOD = 1e9 + 7; ll a[N], res, n; struct edge{ int u, v; }; vector<edge> adj; bool cmp(edge x, edge y){ return max(a[x.u], a[x.v]) < max(a[y.u], a[y.v]); } struct DSU{ ll par[N], sz[N]; void init(ll n){ for (ll i = 1; i <= n; ++i){ sz[i] = 1; par[i] = i; } } ll Find(ll u){ if (u == par[u]) return u; return par[u] = Find(par[u]); } ll Union(ll u, ll v){ u = Find(u); v = Find(v); if (u == v) return 0; ll res = a[u] + a[v]; if (sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; a[u] = max(a[u], a[v]); a[v] = max(a[u], a[v]); return res; } } dsu; int main(){ if(fopen("coci2021_r2_sjekira.inp", "r")){ freopen("coci2021_r2_sjekira.inp", "r", stdin); freopen("coci2021_r2_sjekira.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i){ int u, v; cin >> u >> v; adj.push_back({u, v}); } dsu.init(n); sort(begin(adj), end(adj), cmp); for (edge x : adj){ res += dsu.Union(x.u, x.v); } cout << res; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 5312 KB | Output is correct |
2 | Correct | 21 ms | 4572 KB | Output is correct |
3 | Correct | 19 ms | 4316 KB | Output is correct |
4 | Correct | 23 ms | 5004 KB | Output is correct |
5 | Correct | 39 ms | 5844 KB | Output is correct |
6 | Correct | 36 ms | 5588 KB | Output is correct |
7 | Correct | 30 ms | 5340 KB | Output is correct |
8 | Correct | 28 ms | 5340 KB | Output is correct |
9 | Correct | 18 ms | 4292 KB | Output is correct |
10 | Correct | 36 ms | 5596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2392 KB | Output is correct |
10 | Correct | 1 ms | 2392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 27 ms | 5312 KB | Output is correct |
7 | Correct | 21 ms | 4572 KB | Output is correct |
8 | Correct | 19 ms | 4316 KB | Output is correct |
9 | Correct | 23 ms | 5004 KB | Output is correct |
10 | Correct | 39 ms | 5844 KB | Output is correct |
11 | Correct | 36 ms | 5588 KB | Output is correct |
12 | Correct | 30 ms | 5340 KB | Output is correct |
13 | Correct | 28 ms | 5340 KB | Output is correct |
14 | Correct | 18 ms | 4292 KB | Output is correct |
15 | Correct | 36 ms | 5596 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 1 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2392 KB | Output is correct |
20 | Correct | 1 ms | 2392 KB | Output is correct |
21 | Correct | 8 ms | 3548 KB | Output is correct |
22 | Correct | 6 ms | 3296 KB | Output is correct |
23 | Correct | 34 ms | 5592 KB | Output is correct |
24 | Correct | 23 ms | 5084 KB | Output is correct |
25 | Correct | 24 ms | 5084 KB | Output is correct |
26 | Correct | 15 ms | 4060 KB | Output is correct |
27 | Correct | 19 ms | 4296 KB | Output is correct |
28 | Correct | 22 ms | 4572 KB | Output is correct |
29 | Correct | 15 ms | 3816 KB | Output is correct |
30 | Correct | 38 ms | 5772 KB | Output is correct |