제출 #374465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374465		Araragi	Sjekira (COCI20_sjekira)	C++14	0 / 110	101 ms	2148 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;

int cost[100001];

vector<int> dsu;
int ans;

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

inline bool unite(int x, int y)
{
	int xx = get(x);
	int 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<int, int> x, pair<int, int> 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");

	int n;
	cin >> n;

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

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

   	vector<pair<int, int> > edges;

   	for (int i = 1; i < n; i++)
   	{
   		int 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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60