Cod sursă (job #386724)

#include <bits/stdc++.h>
using namespace std;
const int MAX=100010;
int n,m,k,p[10010],aa,bb,cc,suma,ma;
struct drum
{
    int a,b,c;
};
vector<drum> dr;

bool cmp(drum i,drum j)
{
    return i.c<j.c;
}
int A,B;
int parent(int x)
{
    if(x==p[x])return x;
    else p[x]=parent(p[x]);
    return p[x];
}

int cb(int x)
{
    int st=0,dre=dr.size()-1,mid;
    while(st<=dre)
    {
        mid=(st+dre)/2;
        if(dr[mid].c>=x) dre=mid-1;
        else st=mid+1;
    }
    return dre;
}

int acm(int mm)
{
    for(int i=1;i<=n;i++)p[i]=i;
    for(int i=0,j=0;i<mm && j<n-1;i++)
    {
        A=parent(dr[i].a);
        B=parent(dr[i].b);
        if(A!=B)
        {
            p[A]=B;
            suma+=dr[i].c;
            ma=max(ma,dr[i].c);
            j++;
        }
       // else dr[i].c=MAX;
    }
    return suma;
}
int main()
{
    ifstream cin("zapada.in");
    ofstream cout("zapada.out");
    cin>>n>>m>>k;

    for(int i=0;i<m;i++)
    {
        cin>>aa>>bb>>cc;
        dr.push_back({aa,bb,cc});
    }
    sort(dr.begin(),dr.end(),cmp);
    cout<<acm(m)<<'\n';
    for(int i=0;i<k;i++)
    {
        cin>>aa>>bb>>cc;
        if(cc>ma) cout<<suma<<'\n';
        else
        {
            suma=0;
            dr.insert(dr.begin()+cb(cc)+1,{aa,bb,cc});
        cout<<acm(m+1+i)<<'\n';
        }

    }
    return 0;
}