oj.uz

Submission #13286

# Submission time Handle Problem Language Result Execution time Memory
13286 2015-02-09T15:38:48 Z heesub 비용 (KOI11_cost) C++
7.2 / 24
 1500 ms 4304 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;
}
 
int v, e;
std::vector<edge> edges;
 
int uf[MAX_V + 1];
int rank[MAX_V + 1];
 
static int _find(int v1)
{
    int tmp = v1;
 
    while (v1 != uf[v1])
        v1 = uf[v1];
 
    uf[tmp] = v1;
 
    return v1;
}
 
static void _union(int v1, int v2)
{
    int pv1 = _find(v1);
    int pv2 = _find(v2);
 
    if (pv1 == pv2) return;
 
    if (rank[pv1] > rank[pv2])
        uf[pv2] = pv1;
    else {
        uf[pv1] = pv2;
        if (rank[pv1] == rank[pv2])
            rank[pv2]++;
    }
}
 
static int cost(int v1, int v2)
{
    int i;
    int sum = 0;
 
    if (v1 >= v2)
        return 0;
 
    for (i = 1; i <= v; i++) {
        uf[i] = i;
        rank[i] = 1;
    }
 
    std::vector<edge>::iterator iter;
    for (iter = edges.begin(); iter != edges.end(); iter++) {
        _union(iter->_from, iter->_to);
        if (_find(v1) == _find(v2))
            break;
    }   
 
    for (;iter != edges.end(); iter++)
        sum += iter->_weight;
 
    return sum;
}
 
int main(void)
{
    unsigned long long sum = 0;
 
    scanf("%d", &v);
    scanf("%d", &e);
     
    for (int i = 0; i < e; i++) {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);
        edges.push_back(edge(from, to, weight));
    }
 
    std::sort(edges.begin(), edges.end());
 
    for (int i = 1; i <= v; i++)
        for (int j = 1; j <= v; j++)
            sum += cost(i, j);
 
    if (sum > 1000000000)
        printf("%llu\n", sum % 1000000000);
    else
        printf("%llu\n", sum);
 
    return 0;
}

Subtask #1
4.8 / 4.8

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

Subtask #2
2.4 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1996 KB Output is correct
2 Correct 7 ms 1996 KB Output is correct
3 Execution timed out 1500 ms 1992 KB Program timed out
4 Execution timed out 1500 ms 1992 KB Program timed out
5 Execution timed out 1500 ms 2184 KB Program timed out
6 Execution timed out 1500 ms 2380 KB Program timed out

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1500 ms 2576 KB Program timed out
2 Execution timed out 1500 ms 3152 KB Program timed out
3 Execution timed out 1500 ms 4304 KB Program timed out
4 Execution timed out 1500 ms 2576 KB Program timed out
5 Execution timed out 1500 ms 4304 KB Program timed out
6 Execution timed out 1500 ms 3152 KB Program timed out
7 Execution timed out 1500 ms 4304 KB Program timed out
8 Execution timed out 1500 ms 4304 KB Program timed out
9 Execution timed out 1500 ms 4304 KB Program timed out
10 Execution timed out 1500 ms 4304 KB Program timed out