Cod sursă (job #272039)

#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;
}