Submission #1287657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287657		MinhKien	Sjekira (COCI20_sjekira)	C++20	110 / 110	28 ms	2612 KiB

sjekira

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, a[N];

struct edge {
    int x, y;

    void inp() {
        cin >> x >> y;
    }

    bool operator < (const edge &o) const {
        return max(a[x], a[y]) < max(a[o.x], a[o.y]);
    }
} e[N];

long long ans;
struct DSU {
    int par[N];
    long long mx[N];

    void start() {
        for (int i = 1; i <= n; ++i) {
            par[i] = -1;
            mx[i] = a[i];
        }
    }

    int FindPar(int u) {
        return par[u] < 0 ? u : par[u] = FindPar(par[u]);
    }

    void unite(int u, int v) {
        u = FindPar(u);
        v = FindPar(v);

        if (par[u] > par[v]) swap(u, v);
        ans += mx[u] + mx[v];

        par[u] += par[v];
        par[v] = u;
        mx[u] = max(mx[u], mx[v]);
    }
} dsu;

int main() {
//    freopen("SJEKIRA.INP", "r", stdin);
//    freopen("SJEKIRA.OUT", "w", stdout);

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) e[i].inp();
    sort(e + 1, e + n);

    dsu.start();
    for (int i = 1; i < n; ++i) {
        dsu.unite(e[i].x, e[i].y);
    }

    cout << ans;

    return 0;
}

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