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
#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;
}
# 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
# 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
# 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