제출 #4920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4920		gs13068	비용 (KOI11_cost)	C++98	1.20 / 24	52 ms	3432 KiB

cost

#include<cstdio>
#include<algorithm>

int parent[100001];
int height[100001];
int size[100001];

long long res;

int root(int x){return x==parent[x]?x:parent[x]=root(parent[x]);}

inline void combine(int a,int b,int c)
{
	a=root(a);
	b=root(b);
	if(a==b)(res+=1LL*size[a]*(size[a]-1)/2*c)%=1000000000;
	else if(a!=b)
	{
		(res+=1LL*(size[a]+size[b])*(size[a]+size[b]-1)/2*c)%=1000000000;
		if(height[a]<height[b])
		{
			parent[a]=b;
			size[b]+=size[a];
		}	
		else
		{
			parent[b]=a;
			size[a]+=size[b];
		}
		if(height[a]==height[b])
			height[a]++;
	}
}

struct edge
{
	int s;
	int e;
	int t;
} a[100000];

inline bool operator <(const edge &x,const edge &y)
{
	return x.t>y.t;
}

int main()
{
	int i,n,m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		parent[i]=i;
		size[i]=1;
	}
	for(i=0;i<m;i++)scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].t);
	std::sort(a,a+m);
	for(i=0;i<m;i++)combine(a[i].s,a[i].e,a[i].t);
	printf("%lld\n",res);
}

• Subtask 1: 1.2 / 4.8
• Subtask 2: 0 / 7.2
• Subtask 3: 0 / 12