Submission #1071768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071768		VMaksimoski008	Sjekira (COCI20_sjekira)	C++17	0 / 110	55 ms	4900 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(v.begin(), v.end());
    for(auto &[_, a, b] : edges) uni(a, b);
    cout << ans << '\n';
    return 0;
}

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