Cod sursă (job #749775)

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;


ifstream fin("zapada.in");
ofstream fout("zapada.out");

struct nodi{
    int x,y,dis;
};

vector<int> vf;
vector<nodi> v;
vector<nodi> nece;

int ga(int nod)
{
    if(nod==vf[nod])
        return  nod;
    vf[nod]=ga(vf[nod]);
    return vf[nod];
}

int n;

int tot;
int maxim;

int caut1;
int st;
int dr;
int inline caut()
{
    if(st>=dr)
        return st;
    int mij=(st+dr)>>1;
    if(v[mij].dis==caut1)
        return mij;
    if(v[mij].dis>caut1)
    {
        dr=mij;
        return caut();
    }
    else
    {
        st=mij+1;
        return caut();
    }
}
int N;
void inline kruskal()
{
    tot=0;
    maxim=0;
    int scos=0;
    nece.clear();
    vector<nodi>::iterator el;
    for(el=v.begin();el!=v.end() && scos<N;++el)
    {
        if(ga(vf[el->y])!=ga(vf[el->x]))
        {
            vf[ga(el->x)]=vf[el->y];
            maxim=(maxim>(el->dis)?maxim:(el->dis));
            tot+=(el->dis);
            nece.push_back(*el);
            scos++;
        }
    }
}

int main()
{
    nodi nod;
    int m,K;
    fin>>n>>m>>K;
    N=n-1;
    for(int k=1;k<=m;k++)
    {
        fin>>nod.x>>nod.y>>nod.dis;
        v.push_back(nod);
    }
    sort(v.begin(),v.end(),[](nodi a, nodi b){
            return a.dis<b.dis;
         });
    vf.resize(n+1);
    for(int k=1;k<=n;k++)
        vf[k]=k;
    kruskal();
    fout<<tot<<'\n';
    v=nece;
    for(int k=1;k<=K;++k)
    {
        fin>>nod.x>>nod.y>>nod.dis;
        if(nod.dis<=maxim)
        {
            caut1=nod.dis;
            st=0;
            dr=N;
            v.insert(v.begin()+caut(),nod);
            for(int c=1;c<=n;c++)
                vf[c]=c;
            kruskal();
            fout<<tot<<'\n';
            v=nece;
        }
        else
            fout<<tot<<'\n';
    }
}