Submission #513119

#	Time	Username	Problem	Language	Result	Execution time	Memory
513119		KoD	Sjekira (COCI20_sjekira)	C++17	110 / 110	53 ms	4376 KiB

sjekira

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

struct UnionFind {
    vector<int> par;
    UnionFind(const int n) : par(n, -1) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return x;
        if (par[x] > par[y]) std::swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return x;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> C(N);
    for (auto& x : C) {
        std::cin >> x;
    }
    vector<tuple<int, int, int>> edge(N - 1);
    for (auto& [c, x, y] : edge) {
        std::cin >> x >> y;
        x -= 1, y -= 1;
        c = std::max(C[x], C[y]);
    }
    std::sort(edge.begin(), edge.end());
    UnionFind dsu(N);
    long long ans = 0;
    for (auto& [c, x, y] : edge) {
        x = dsu.find(x), y = dsu.find(y);
        ans += C[x] + C[y];
        const int z = dsu.merge(x, y);
        C[z] = std::max(C[x], C[y]);
    }
    std::cout << ans << '\n';
    return 0;
}

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