Submission #13309

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13309	2015-02-11T15:57:14 Z	heesub	비용 (KOI11_cost)	C++	24 / 24	64 ms	4692 KB

cost

#include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX_V	100000
#define MAX_E	100000

class edge {
public:
	edge(int from, int to, int weight)
	{
		_from = from;
		_to = to;
		_weight = weight;
	}

	int _from;
	int _to;
	int _weight;
};

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

std::vector<edge> edges;

int uf[MAX_V + 1];
int rank[MAX_V + 1];
int adj[MAX_V + 1];

static int _find(int v1)
{
	int tmp = v1;

	while (v1 != uf[v1])
		v1 = uf[v1];

	uf[tmp] = v1;

	return v1;
}

static unsigned int _union(int v1, int v2)
{
	int ret = 0;
	int pv1 = _find(v1);
	int pv2 = _find(v2);

	/* already connected */
	if (pv1 == pv2) return ret;

	ret = adj[pv1] * adj[pv2];

	if (rank[pv1] > rank[pv2]) {
		uf[pv2] = pv1;
		adj[pv1] += adj[pv2];
	}
	else {
		uf[pv1] = pv2;
		adj[pv2] += adj[pv1];
		if (rank[pv1] == rank[pv2])
			rank[pv2]++;
	}

	return ret;
}

int main(void)
{
	int nr_vertices, nr_edges;
	unsigned long long sum = 0, total = 0;

	scanf("%d %d", &nr_vertices, &nr_edges);
	
	for (int i = 0; i < nr_edges; i++) {
		int from, to, weight;
		scanf("%d %d %d", &from, &to, &weight);
		edges.push_back(edge(from, to, weight));
		total += weight;
	}

	std::sort(edges.begin(), edges.end());

	/* initialize uf */
	for (int i = 1; i <= nr_vertices; i++) {
		uf[i] = i;
		adj[i] = rank[i] = 1;
	}

	for (std::vector<edge>::iterator iter = edges.begin(); iter != edges.end(); iter++) {
		sum += _union(iter->_from, iter->_to) * total;
		total -= iter->_weight;
	}

	printf("%llu\n", sum % 1000000000);

	return 0;
}

Subtask #1

4.8 / 4.8

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

Subtask #2

7.2 / 7.2

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

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	2964 KB	Output is correct
2	Correct	13 ms	3540 KB	Output is correct
3	Correct	59 ms	4692 KB	Output is correct
4	Correct	8 ms	2964 KB	Output is correct
5	Correct	61 ms	4692 KB	Output is correct
6	Correct	34 ms	3540 KB	Output is correct
7	Correct	64 ms	4692 KB	Output is correct
8	Correct	49 ms	4692 KB	Output is correct
9	Correct	64 ms	4692 KB	Output is correct
10	Correct	63 ms	4692 KB	Output is correct