Cod sursă (job #615376)

#include <iostream>
#include <fstream>
#include <vector>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define maxi 10000
using namespace std;
struct muchie{
   int x;
   int y;
   int cost;
};
vector<pair<int,int>> V[maxi+5];
vector<pair<int,int>>::iterator I,I2;
vector<muchie> v;
vector<muchie>::iterator i1,i2;
bool viz[maxi+5];
int n,m,k,a,b,c,RANG[maxi+5],R[maxi+5],tata[maxi+5],cost[maxi+5],lvl[maxi+5];
long long APM;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};
bool CMP(muchie A,muchie B)
{
    return(A.cost<B.cost);
}
int REP(int x)
{
    if(x==R[x])
        return x;
    else return REP(R[x]);
}
void UNIRE(int x,int y)
{
    if(RANG[x]>RANG[y])
    {
        R[y]=x;
    }
    if(RANG[y]>RANG[x])
    {
        R[x]=y;
    }
    if(RANG[x]==RANG[y])
    {
        R[y]=x;
        RANG[x]++;
    }
}
void INIT()
{
    for(int i=1;i<=n;i++)
        R[i]=i,RANG[i]=1;
}
void KRUSKAL()
{
    INIT();
    i1=v.begin();
    i2=v.end();
    sort(i1,i2,CMP);
    for(auto a:v)
    {
        int rx=REP(a.x);
        int ry=REP(a.y);
        if(rx!=ry)
        {
            UNIRE(rx,ry);
            APM+=a.cost;
            V[a.x].push_back(make_pair(a.y,a.cost));
            V[a.y].push_back(make_pair(a.x,a.cost));
        }

    }

}
void DFS(int x,int lv)
{
    viz[x]=true;
    lvl[x]=lv;
    for(auto a:V[x])
    {
        if(!viz[a.first])
        {
            tata[a.first]=x;
            cost[a.first]=a.second;
            DFS(a.first,lv+1);
        }
    }
}
void LCA(int x,int y,int&cmax,int&e1,int&e2)
{
    while(x!=y)
    {
        if(lvl[x]>lvl[y])
        {
            if(cmax<cost[x])
            {
                cmax=cost[x];
                e1=x;
                e2=tata[x];
            }
            x=tata[x];
        }
        else{
             if(cmax<cost[y])
            {
                cmax=cost[y];
                e1=y;
                e2=tata[y];
            }
            y=tata[y];
        }
    }
}
int main()
{
    InParser f("zapada.in");
    OutParser g("zapada.out");
    f>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v.push_back({a,b,c});
    }
    KRUSKAL();
    g<<APM<<'\n';
    for(int i=1;i<=k;i++)
    {
        f>>a>>b>>c;
        memset(viz,0,sizeof(viz));
        memset(tata,0,sizeof(tata));
        memset(lvl,0,sizeof(lvl));
        memset(cost,0,sizeof(cost));
    DFS(1,0);
    int e1=0,e2=0,cmax=0;
    LCA(a,b,cmax,e1,e2);
    if(cmax>c)
    {
        ///elimin [e1,e2]
        ///adaug [a,b]
        I=V[e1].begin();
     for(int i=0;i<V[e1].size();i++)
   {
       if(V[e1][i].second==cmax)
        I2=I;
       I++;
   }
     V[e1].erase(I2);

     I=V[e2].begin();
     for(int i=0;i<V[e2].size();i++)
   {
       if(V[e2][i].second==cmax)
        I2=I;
       I++;
   }
     V[e2].erase(I2);
     V[a].push_back(make_pair(b,c));
     V[b].push_back(make_pair(a,c));
     APM=APM-cmax+c;
    }
    g<<APM<<'\n';
    }
    return 0;
}