| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 464728 | TheScrasse | Sjekira (COCI20_sjekira) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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;}