Submission #866349

#	Time	Username	Problem	Language	Result	Execution time	Memory
866349		vjudge1	Sjekira (COCI20_sjekira)	C++14	110 / 110	23 ms	8496 KiB

sjekira

#include<algorithm>
#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
typedef long long ll;
const int maxn=100000;
int n,t[maxn+1],p[maxn+1];
int head[maxn+1],total;
struct Edge{
	int to,next;
}e[(maxn-1)*2+1];
void add(const int u,const int v){
	e[++total]=Edge{v,head[u]};
	head[u]=total;
}
int fa[maxn+1],val[maxn+1],size[maxn+1];
ll ans;
int find(const int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	ans+=val[x]+val[y];
	if(size[x]>size[y]){
		fa[y]=x;
		val[x]=std::max(val[x],val[y]);
		size[x]+=size[y];
	}else{
		fa[x]=y;
		val[y]=std::max(val[y],val[x]);
		size[y]+=size[x];
	}
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)read(t[i]);
	for(int i=1;i<=n;i++)p[i]=i;
	memcpy(fa+1,p+1,sizeof(int)*n);
	memcpy(val+1,t+1,sizeof(int)*n);
	for(int i=1;i<=n;i++)size[i]=1;
	std::sort(p+1,p+n+1,[](const int x,const int y){
		return t[x]<t[y];
	});
	for(int i=1,x,y;i<n;i++){
		read(x),read(y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		const int u=p[i];
		for(int i=head[u];i;i=e[i].next){
			const int v=e[i].to;
			if(t[v]<t[u]||(t[v]==t[u]&&v<u))merge(u,v);
		}
	}
	write(ans),pc('\n');
	return 0;
}

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