oj.uz

Submission #4942

# Submission time Handle Problem Language Result Execution time Memory
4942 2014-01-22T05:44:59 Z cki86201 비용 (KOI11_cost) C++
24 / 24
 52 ms 2924 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;

const int MOD = 1e9;
typedef long long ll;

struct edge{
	int st,en,len;
	bool operator<(const edge &l)const{
		return len<l.len;
	}
}inp[100010];

int n, m;
ll ans;
ll now;

struct UnF{
	int p[100010];
	int w[100010];
	void init(){for(int i=0;i<n;i++)p[i] = i, w[i] = 1;}
	int Find(int x){
		if(p[x] == x)return x;
		return p[x] = Find(p[x]);
	}
	int Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x==y)return (int)now;
		now -= (ll)w[x] * (w[x] - 1) / 2 + (ll)w[y] * (w[y] - 1) / 2;
		now += (ll)(w[x] + w[y]) * (w[x] + w[y] - 1) / 2;
		now %= MOD;
		if(w[x] > w[y])p[y] = x, w[x] += w[y];
		else p[x] = y, w[y] += w[x];
		return (int)now;
	}
};

int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=0;i<m;i++)scanf("%d%d%d",&inp[i].st,&inp[i].en,&inp[i].len);
	sort(inp,inp+m);
	UnF uf;
	uf.init();
	for(i=m-1;i>=0;i--)ans += (ll)inp[i].len * uf.Union(inp[i].st, inp[i].en), ans %= MOD;
	printf("%lld",ans);
	return 0;
}

Subtask #1
4.8 / 4.8

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

Subtask #2
7.2 / 7.2

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2916 KB Output is correct
2 Correct 16 ms 2916 KB Output is correct
3 Correct 40 ms 2916 KB Output is correct
4 Correct 4 ms 2916 KB Output is correct
5 Correct 48 ms 2920 KB Output is correct
6 Correct 24 ms 2920 KB Output is correct
7 Correct 48 ms 2920 KB Output is correct
8 Correct 48 ms 2916 KB Output is correct
9 Correct 52 ms 2916 KB Output is correct
10 Correct 44 ms 2920 KB Output is correct