Submission #4921

#	Time	Username	Problem	Language	Result	Execution time	Memory
4921		gs13068	비용 (KOI11_cost)	C++98	7.20 / 24	44 ms	3432 KiB

cost

#include<cstdio>
#include<algorithm>

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

int 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+=size[a]*size[b]*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;
	long long temp=0;
	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);
		temp+=a[i].t;
	}
	std::sort(a,a+m);
	for(i=0;i<m;i++)
	{
		combine(a[i].s,a[i].e,temp);
		temp-=a[i].t;
	}
	printf("%d\n",res);
}

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