oj.uz

Submission #5370

# Submission time Handle Problem Language Result Execution time Memory
5370 2014-04-16T08:12:42 Z baneling100 비용 (KOI11_cost) C++
24 / 24
 52 ms 3040 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef pair <int,int> ppair;
pair <int,ppair> road[100001];
int n, m, anc[100001], cnt[100001];
long long ans, hab;

void input(void)
{
    int i, x, y, w;

    scanf("%d %d",&n,&m);
    for(i=1 ; i<=m ; i++)
    {
        scanf("%d %d %d",&x,&y,&w);
        hab+=w;
        road[i]=make_pair(w,make_pair(x,y));
    }
    sort(road+1,road+m+1);
    for(i=1 ; i<=n ; i++)
        cnt[i]=1;
}

int find_anc(int x)
{
    while(anc[x]>0)
    {
        x=anc[x];
    }
    return x;
}

void process(void)
{
    int i, a1, a2;

    for(i=m ; i>=1 ; i--)
    {
        a1=find_anc(road[i].second.first);
        a2=find_anc(road[i].second.second);
        if(a1!=a2)
        {
            ans+=(long long)cnt[a1]*(long long)cnt[a2]*hab;
            ans%=1000000000;
            if(a1<a2)
            {
                anc[a2]=a1;
                cnt[a1]+=cnt[a2];
            }
            else
            {
                anc[a1]=a2;
                cnt[a2]+=cnt[a1];
            }
        }
        hab-=road[i].first;
    }
}

void output(void)
{
    printf("%lld",ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

Subtask #1
4.8 / 4.8

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

Subtask #2
7.2 / 7.2

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3040 KB Output is correct
2 Correct 20 ms 3040 KB Output is correct
3 Correct 48 ms 3040 KB Output is correct
4 Correct 8 ms 3040 KB Output is correct
5 Correct 44 ms 3040 KB Output is correct
6 Correct 24 ms 3040 KB Output is correct
7 Correct 52 ms 3040 KB Output is correct
8 Correct 48 ms 3040 KB Output is correct
9 Correct 36 ms 3040 KB Output is correct
10 Correct 48 ms 3040 KB Output is correct