Submission #861133

#	Time	Username	Problem	Language	Result	Execution time	Memory
861133		vjudge1	Sjekira (COCI20_sjekira)	C++14	110 / 110	22 ms	6740 KiB

sjekira

#include<algorithm>
#include<cstdio>
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
const int maxn=100005;
int n,total,head[maxn],to[maxn<<1],next[maxn<<1];
void add(int u,int v){
	to[++total]=v;
	next[total]=head[u];
	head[u]=total;
}
struct Node{
	int t,id;
}node[maxn];
bool operator<(Node a,Node b){
	return a.t==b.t?a.id<b.id:a.t<b.t;
}
int fa[maxn],max[maxn];
void clear(){
	for(int i=1;i<=n;i++)fa[i]=i,max[i]=node[i].t;
}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	max[y]=max[x]>max[y]?max[x]:max[y];
	fa[x]=y;
}
int rank[maxn];
long long answer;
int main(){
	n=read();
	for(int i=1;i<=n;i++)node[i]=Node{read(),i};
	int u,v;
	for(int i=1;i<n;i++){
		u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	clear();
	std::sort(node+1,node+n+1);
	for(int i=1;i<=n;i++)rank[node[i].id]=i;
	for(int i=1;i<=n;i++){
		u=node[i].id;
		for(int j=head[u];j;j=next[j]){
			v=to[j];
			if(rank[u]>rank[v])answer+=max[find(u)]+max[find(v)],merge(v,u);
		}
	}
	printf("%lld",answer); 
	return 0;
}

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