제출 #374312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374312		Vimmer	Sjekira (COCI20_sjekira)	C++14	110 / 110	56 ms	2412 KiB

sjekira

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define N 100005
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

int p[N], mx[N];

int fnd(int x)
{
    if (p[x] != x)
        p[x] = fnd(p[x]);

    return p[x];
}

void link(int a, int b)
{
    p[b] = a;

    mx[a] = max(mx[a], mx[b]);
}

int a[N];

bool cmp(pair <int, int> x, pair <int, int> y)
{
    return max(a[x.F], a[x.S]) < max(a[y.F], a[y.S]);
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("1.in", "r", stdin);

    int n;

    cin >> n;

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

    vector <pair <int, int> > pr(n - 1);

    for (int i = 1; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        pr[i - 1] = {x, y};
    }

    sort(all(pr), cmp);

    for (int i = 1; i <= n; i++)
        {
            p[i] = i;

            mx[i] = a[i];
        }

    ll ans = 0;

    for (auto it : pr)
    {
        int l = fnd(it.F), r = fnd(it.S);

        ans += mx[l] + mx[r];

        link(l, r);
    }

    pri(ans);
}

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