제출 #1165684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165684		kerem	Sjekira (COCI20_sjekira)	C++20	110 / 110	39 ms	10428 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
#define N 100000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int dsu[N+5],d[N+5],a[N+5];
vector<int> g[N+5];

int find(int x){
	if(dsu[x]<0)
		return x;
	return dsu[x]=find(dsu[x]);
}
int comb(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y)
		return 0;
	int t=d[x]+d[y];
	d[x]=max(d[x],d[y]);
	dsu[y]=x;
	return t;
}
void solve(){
	memset(dsu,-1,sizeof(dsu));
	int n;
	cin >> n;
	vector<pii> v;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		d[i]=a[i];
		v.pb({a[i],i});
	}
	sort(all(v));
	for(int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	int ans=0;
	for(auto [h,i]:v)
		for(auto j:g[i])
			if(a[j]<=h)
				ans+=comb(i,j);
	cout << ans << endl;
}
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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