Submission #1154024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154024		yhkhoo	Sjekira (COCI20_sjekira)	C++20	110 / 110	25 ms	2376 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second

const int MAXN = 100005;

int p[MAXN], g[MAXN], t[MAXN];

int par(int u){
    if(p[u] == u) return u;
    p[u] = par(p[u]);
    return p[u];
}

int onion(int u, int v){
    u = par(u); v = par(v);
    assert(u != v);
    if(v > u) swap(u, v);
    int ret = g[u] + g[v];
    g[v] = max(g[v], g[u]);
    p[u] = v;
    return ret;
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        p[i] = i;
        cin >> t[i];
        g[i] = t[i];
    }
    pii a[n-1];
    for(int i=0, x, y; i<n-1; i++){
        cin >> a[i].fi >> a[i].se;
        a[i].fi--; a[i].se--;
    }
    sort(a, a+n-1, [](const pii &a, const pii &b){
        return max(t[a.fi], t[a.se]) < max(t[b.fi], t[b.se]);
    });
    long long ans = 0;
    for(int i=0; i<n-1; i++){
        ans += onion(a[i].fi, a[i].se);
    }
    cout << ans;
    return 0;
}

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