Submission #876889

#	Time	Username	Problem	Language	Result	Execution time	Memory
876889		overwatch9	Sjekira (COCI20_sjekira)	C++17	110 / 110	110 ms	10068 KiB

sjekira

//subtask3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
vector <vector <int>> adj;
vector <int> vals;
struct DSU {
    vector <int> link, sz, mx_val;
    DSU (int s) {
        link = sz = mx_val = vector <int> (s+1);
        for (int i = 1; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
            mx_val[i] = vals[i];
        }
    }
    int head(int x) {
        while (x != link[x])
            x = link[x];
        return x;
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (a == b)
            return;
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += sz[b];
        link[b] = a;
        mx_val[a] = max(mx_val[a], mx_val[b]);
    }
    ll get_mx_val(int x) {
        return mx_val[head(x)];
    }
};
bool comp(int a, int b) {
    return vals[a] < vals[b];
}
int main() {
    int n;
    cin >> n;
    vals.resize(n+1);
    adj.resize(n+1);
    for (int i = 1; i <= n; i++)
        cin >> vals[i];
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DSU dsu(n+1);
    vector <int> ord(n+1);
    for (int i = 1; i <= n; i++)
        ord[i] = i;
    sort(ord.begin(), ord.end(), comp);
    vector <bool> activated(n+1);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int id = ord[i];
        activated[id] = true;
        ll added = 0;
        for (auto j : adj[id]) {
            if (activated[j]) {
                added++;
                ans += dsu.get_mx_val(j);
                dsu.unite(j, id);
            }
        }
        ans += added * vals[id];
    }
    cout << ans << '\n';
}

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