제출 #1271996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271996		flaming_top1	Sjekira (COCI20_sjekira)	C++20	110 / 110	31 ms	3492 KiB

sjekira

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n;
lint a[100005];
pair<int, int> edges[100005];

struct Dsu
{
    int par[100005], sz[100005];
    lint maxi[100005];

    void setup()
    {
        for (int i = 1; i <= n; i++)
        {
            sz[i] = 1;
            par[i] = i;
            maxi[i] = a[i];
        }
    }

    int find_par(int now)
    {
        return par[now] == now ? now : par[now] = find_par(par[now]);
    }

    void combine(int l, int r)
    {
        l = find_par(l);
        r = find_par(r);
        if (l == r)
            return;
        if (sz[l] < sz[r])
            swap(l, r);
        par[r] = l;
        sz[l] += sz[r];
        maxi[l] = max(maxi[l], maxi[r]);
    }

} dsu;

bool cmp(pair<int, int> jack, pair<int, int> mck)
{
    return max(a[jack.fi], a[jack.se]) < max(a[mck.fi], a[mck.se]);
}

fami lore()
{
    SPED;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        edges[i] = {l, r};
    }
    dsu.setup();
    sort(edges + 1, edges + n, cmp);

    lint res = 0;
    for (int i = 1; i < n; i++)
    {
        auto [u, v] = edges[i];
        u = dsu.find_par(u);
        v = dsu.find_par(v);

        // if (u == v)
        //     continue;

        res += dsu.maxi[u] + dsu.maxi[v];
        dsu.combine(u, v);
    }

    cout << res;
}
// Let your soul wander where dreams are born.

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