제출 #1071785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071785		VMaksimoski008	Sjekira (COCI20_sjekira)	C++17	110 / 110	72 ms	5576 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int maxn = 1e5 + 5;
 
ll ans = 0;
int par[maxn], sz[maxn], mx[maxn];
 
int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}
 
void uni(int a, int b) {
    a = find(a); b = find(b);
    ans += mx[a] + mx[b];
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    mx[a] = max(mx[a], mx[b]);
    par[b] = a;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1, mx[i] = v[i];
 
    vector<array<int, 3> > edges;
    for(int i=0; i<n-1; i++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({ max(v[a], v[b]), a, b });
    }
 
    sort(edges.begin(), edges.end());
    for(auto &[_, a, b] : edges) uni(a, b);
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60