제출 #374468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374468		Araragi	Sjekira (COCI20_sjekira)	C++17	110 / 110	125 ms	4448 KiB

sjekira

/*
* 	author: Araragi
*/

// 3

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

ll cost[100001];

vector<ll> dsu;
ll ans;

inline ll get(ll x)
{
	return (dsu[x] == x ? x : dsu[x] = get(dsu[x]));
}

inline bool unite(ll x, ll y)
{
	ll xx = get(x);
	ll yy = get(y);

	if (xx != yy)
	{
		dsu[xx] = yy;

		ans += cost[xx];
        ans += cost[yy];

        cost[yy] = max(cost[yy], cost[xx]);

		return true;
	}

	return false;
}

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

int main()
{
	//ifstream cin("vacation.in");
	//ofstream cout("vacation.out");

	ll n;
	cin >> n;

	for (ll i = 1; i <= n; i++)
		cin >> cost[i];

	dsu.resize(n + 1);
	iota(dsu.begin(), dsu.end(), 0);

   	vector<pair<ll, ll> > edges;

   	for (ll i = 1; i < n; i++)
   	{
   		ll x, y;
   		cin >> x >> y;
   		edges.pb({x, y});
   	}

   	sort(edges.begin(), edges.end(), cmp);

   	for (auto edge : edges)
   		if (unite(edge.F, edge.S))
   		{
   		    // without code, need void
   		}

   	cout << ans;
}

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