Cod sursă (job #271967)

#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;
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],mk1[10005];

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 mu=0,i,x,y,ok=0;
   i=1;  muchie aux;
   int pos=n;
   unsigned long long sum=0;
    while(mu<n-1)
    {
        if( ok==0 && mk[n].c<mk[i].c)
        { x=Find(mk[n].a);
            y=Find(mk[n].b);
            if(x!=y)  {  mu++; sum+=mk[n].c; Union(x,y);  }
            ok=1;
        }

        x=Find(mk[i].a);
        y=Find(mk[i].b);
        if(x!=y)
        {mu++;
          sum+=mk[i].c;
            Union(x,y);
        }
        else pos=i;
        i++;
    }
    if(pos!=n)  mk[pos]=mk[n];
    i=pos;
    while(i<n && mk[i].c>mk[i+1].c) { aux=mk[i]; mk[i]=mk[i+1]; mk[i]=aux; i++;   }
    memset(t,0,sizeof(t));
    memset(niv,0,sizeof(niv));
    fprintf(g,"%llu\n",sum);
    ct=sum;
}

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++)
    {  //if(ok==0) for(j=1;j<=n-1;j++)
         //  mk[j]=mk1[j];
       //j=n;
      // if(i==2) fprintf(g,"%d\n",mk[n-1].c);
        mk[n].a=read(f);
        mk[n].b=read(f);
        mk[n].c=read(f);
        //mk1[n]=mk[j];
        //sort(mk+1,mk+n+1,cp);
        if(mk[n].c>=mk[n-1].c) {fprintf(g,"%llu\n",ct);  }
        else  { sort(mk+1,mk+n,cp);apm2();}
    }
    return 0;
}