oj.uz

Submission #4924

# Submission time Handle Problem Language Result Execution time Memory
4924 2014-01-09T13:21:24 Z gs13068 비용 (KOI11_cost) C++
24 / 24
 48 ms 3432 KB 
#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,long long c)
{
	a=root(a);
	b=root(b);
	if(a!=b)
	{
		(res+=1LL*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%1000000000);
		temp-=a[i].t;
	}
	printf("%d\n",res);
}

Subtask #1
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3432 KB Output is correct
2 Correct 0 ms 3432 KB Output is correct
3 Correct 0 ms 3432 KB Output is correct
4 Correct 0 ms 3432 KB Output is correct

Subtask #2
7.2 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3432 KB Output is correct
2 Correct 0 ms 3432 KB Output is correct
3 Correct 0 ms 3432 KB Output is correct
4 Correct 0 ms 3432 KB Output is correct
5 Correct 0 ms 3432 KB Output is correct
6 Correct 4 ms 3432 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3432 KB Output is correct
2 Correct 20 ms 3432 KB Output is correct
3 Correct 40 ms 3432 KB Output is correct
4 Correct 8 ms 3432 KB Output is correct
5 Correct 44 ms 3432 KB Output is correct
6 Correct 20 ms 3432 KB Output is correct
7 Correct 44 ms 3432 KB Output is correct
8 Correct 44 ms 3432 KB Output is correct
9 Correct 44 ms 3432 KB Output is correct
10 Correct 48 ms 3432 KB Output is correct