Submission #854479

#	Time	Username	Problem	Language	Result	Execution time	Memory
854479		vjudge1	Sjekira (COCI20_sjekira)	C++17	110 / 110	56 ms	10156 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>

const int N = 1e5+1;

vi a(N),dad(N),mx(N);

int find(int x) {
	if (x == dad[x]) return x;
	return dad[x] = find(dad[x]);
}

void unite(int x,int y) {
	mx[find(x)] = max(mx[find(x)],mx[find(y)]);
	dad[find(x)] = find(y);
}

void solve() {
	int n;
	cin >> n;
	for (int i=1;i<=n;i++) dad[i] = i;
	F(i,n) cin >> a[i];
	F(i,n) mx[i] = a[i];
	vector<int> edg[n+1];
	for (int i=1;i<=n-1;i++) {
		int x,y;
		cin >> x >> y;
		if (a[x] > a[y]) edg[x].pb(y);
		else edg[y].pb(x);
	}
	vi node(n+1);
	F(i,n) node[i] = i;
	sort(node.begin()+1,node.end(),[&](int p,int r) {return a[p]<a[r];});
	int ans = 0;
	for (int i=1;i<=n;i++) { 
		ans+=edg[node[i]].size()*a[node[i]];
		int sm = 0;
		for (auto it : edg[node[i]]) {
			sm+=mx[find(it)];
			unite(it,node[i]);
		}
		ans+=sm;
	}
	cout << ans << endl;
}     
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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