제출 #807171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807171		tlnk07	Sjekira (COCI20_sjekira)	C++17	110 / 110	86 ms	6476 KiB

sjekira

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

long long n, a[100001], p[100001], sz[100001], sum = 0;
pair<int, pair<int, int>> edge[100001];

int findparent(int x)
{
	if(x == p[x])	return x;
	else	return p[x] = findparent(p[x]);
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		p[i] = i;
		sz[i] = a[i];
	}
	for(int i = 1; i < n; ++i)
	{
		cin >> edge[i].second.first >> edge[i].second.second;
		edge[i].first = max(a[edge[i].second.first], a[edge[i].second.second]);
	}
	sort(edge + 1, edge + n);
	for(int i = 1; i < n; ++i)
	{
		long long a = findparent(edge[i].second.first), b = findparent(edge[i].second.second);
		sum = sum + sz[a] + sz[b];
		if(a != b)
		{
			p[a] = b;
			sz[b] = max(sz[a], sz[b]);
		}
	}
	cout << sum;
}

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