# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
13309 |
2015-02-11T15:57:14 Z |
heesub |
비용 (KOI11_cost) |
C++ |
|
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 |