Cod sursă (job #293789)

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#define BUF_SIZE 150000

using namespace std;
FILE *f=fopen("zapada.in","r");
FILE *g=fopen("zapada.out","w");
struct muchie {unsigned short int a,b; int c; };
int n,m,k;
muchie last;
unsigned long long ct=0;
int pos=BUF_SIZE;
char buf[BUF_SIZE];

inline char getChar(FILE *f)
{ if(pos==BUF_SIZE)
{ fread(buf,1,BUF_SIZE,f);
    pos=0;
}
    return buf[pos++];
}

inline int read(FILE *f)
{ int result=0;
    char c;
    do
    {
        c=getChar(f);
    }while(!isdigit(c));
    do
    { result=10 *result+c-'0';
        c=getChar(f);
    }while(isdigit(c));
    return result;
}
muchie  mk[100005];

unsigned short int t[10105],niv[10105];
inline bool cp(muchie m1,muchie m2)
{
    return m1.c<m2.c;
}
inline unsigned short int Find(unsigned short int x)
{
    while(t[x]!=0) x=t[x];
    return x;
}
inline void Union(unsigned short int x,unsigned short int y)
{ if(niv[x]>niv[y]) t[y]=x;
else { t[x]=y;
    if(niv[x]==niv[y]) niv[y]++;
}
}
inline void apm()
{ int mu=0,i,x,y;
    i=1;
    unsigned long long sum=0;
    while(mu<n-1)
    {
        x=Find(mk[i].a);
        y=Find(mk[i].b);
        if(x!=y)
        {mu++;
            sum+=mk[i].c;
            mk[mu]=mk[i];
            Union(x,y);
        }
        i++;
    }
    memset(t,0,sizeof(t));
    memset(niv,0,sizeof(niv));
    fprintf(g,"%llu\n",sum);
    ct=sum;
}
void apm2()
{ int ok,i;
    ok = false;  int x, y; bool ok2 = false; int Ret,Pos;
    long long  Cost = 0;
    for(int i = 1; i <= n - 1; ++i){
        if(last.c < mk[i].c && ok2 == false){
            ok2 = true;
            x = Find(last.a);
            y = Find(last.b);
            if(x != y){
                Union(x, y);
                Cost += last.c;
                ok = true;
                Ret = i;
            }
        }
        x = Find(mk[i].a);
        y = Find(mk[i].b);
        if(x != y){
            Union(x, y);
            Cost += mk[i].c;
        }else{ Pos = i; }
    }
    if(ok){
        for(int i = Pos; i >= Ret; --i)
            mk[i] = mk[i - 1];
        mk[Ret] = last;
    }
    fprintf(g,"%llu\n",Cost);
    memset(t,0,sizeof(t));
    memset(niv,0,sizeof(niv));
    
}

int main()
{  n=read(f);
    m=read(f);
    k=read(f);
    int i,j,ok=0;
    for(i=1;i<=m;i++)
    { mk[i].a=read(f);
        mk[i].b=read(f);
        mk[i].c=read(f);
    }
    sort(mk+1,mk+m+1,cp);
    
    
    apm();
    
    
    for(i=1;i<=k;i++)
    {   last.a=read(f);
        last.b=read(f);
        last.c=read(f);
        apm2();
    }
    return 0;
}