Submission #5370

#	Time	Username	Problem	Language	Result	Execution time	Memory
5370		baneling100	비용 (KOI11_cost)	C++98	24 / 24	52 ms	3040 KiB

cost

#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
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12