제출 #374365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374365		topovik	Sjekira (COCI20_sjekira)	C++14	40 / 110	1073 ms	4448 KiB

sjekira

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 1e6 + 100;
const ll oo = 1e10;

ll a[N];
ll pred[N];
ll r[N];

ll cmp(ll x)
{
    if (x == pred[x]) return x;
    else return (pred[x] = cmp(pred[x]));
}

void unite(ll x, ll y)
{
    if (r[x] > r[y]) pred[y] = x;
    else
    {
        pred[x] = y;
        r[y] += (r[x] == r[y]);
    }
    a[y] = max(a[y], a[x]);
    a[x] = max(a[x], a[y]);
}

int main()
{
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < n; i++) pred[i] = i, r[i] = 0;
    vector <pair<ll, ll> > rebra;
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y;
        cin >> x >> y;
        rebra.pb({--x, --y});
    }
    bool mrk[n - 1];
    for (ll i = 0; i < n - 1; i++) mrk[i] = 0;
    ll ans = 0;
    for (ll i = 0; i < n - 1; i++)
    {
        ll mx1 = oo, nom = -1;
        for (ll j = 0; j < n - 1; j++)
            if (!mrk[j])
        {
            ll x = rebra[j].f, y = rebra[j].s;
            if (a[cmp(x)] + a[cmp(y)] < mx1) mx1 = a[cmp(x)] + a[cmp(y)], nom = j;
        }
        ans += mx1;
        mrk[nom] = 1;
        unite(cmp(rebra[nom].f), cmp(rebra[nom].s));
    }
    cout << ans;
}

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