| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 464728 | TheScrasse | Sjekira (COCI20_sjekira) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// coci2020_2_4// Sjekira#include <bits/stdc++.h>using namespace std;#define nl "\n"#define nf endl#define ll long long#define pb push_back#define _ << ' ' <<#define INF (ll)1e18#define mod 998244353#define maxn 100010ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;ll w[maxn], mx[maxn], parent[maxn];vector<array<ll, 4>> v;ll find(ll x) { if (x == parent[x]) return x; return parent[x] = find(parent[x]);}void merge(ll a, ll b) { a = find(a); b = find(b); res += mx[a] + mx[b]; parent[b] = a; mx[a] = max(mx[a], mx[b]);}int main() { ios::sync_with_stdio(0); cin.tie(0); /* #if !ONLINE_JUDGE && !EVAL ifstream cin("input.txt"); ofstream cout("output.txt"); #endif */ cin >> n; for (i = 1; i <= n; i++) { cin >> w[i]; } for (i = 0; i < n - 1; i++) { cin >> a >> b; if (w[a] < w[b]) swap(a, b); v.pb({w[a], w[b], a, b}); } sort(v.begin(), v.end()); for (i = 1; i <= n; i++) { parent[i] = i; mx[i] = w[i]; } for (auto u : v) { merge(u[2], u[3]); } cout << res << nl; return 0;}