Cod sursă (job #441139)

#include <bits/stdc++.h>
#define max(a,b) (((a)>(b))?(a):(b))

int n, m, k, cmax, costArbore;
int mcx[101010], mcy[101010], costmc[101010], indicemc[101010], compConex[10005];

inline bool cmp(int a, int b)
{
    return costmc[a] < costmc[b];
}

inline int grupa(int x)
{
    if (compConex[x] == x)
        return x;
    return compConex[x] = grupa(compConex[x]);
}

inline void reunire(int x, int y)
{
    compConex[grupa(x)] = grupa(y);
}

inline int cautBin(int lim)
{
    int poz = 1;
    for (int pas = 1 << 17; pas >= 1; pas >>= 1)
    {
        if (poz + pas <= m && costmc[indicemc[poz + pas]] <= lim)
            poz += pas;
    }
    return poz;
}


inline void generareAPM()
{
    for (int i = 1; i <= n; ++i)
        compConex[i] = i;
    cmax = 0;
    costArbore = 0;
    int nrMuchii = 0;
    for (int i = 1; nrMuchii < n - 1; ++i)
    {
        int x = mcx[indicemc[i]];
        int y = mcy[indicemc[i]];
        int c = costmc[indicemc[i]];
        if (grupa(x) != grupa(y))
        {
            ++nrMuchii;
            costArbore += c;
            cmax = max(cmax, c);
            reunire(x, y);
        }
    }
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("zapada.in", "r");
    fout = fopen("zapada.out", "w");
    int x, y, c;
    fscanf(fin, "%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i)
    {
        indicemc[i] = i;
        fscanf(fin, "%d%d%d", &mcx[i], &mcy[i], &costmc[i]);
    }
    std::sort(indicemc + 1, indicemc + m + 1, cmp);
    generareAPM();
    fprintf(fout, "%d\n", costArbore);
    for (int q = 1; q <= k; ++q)
    {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        if (cmax < c)
            fprintf(fout,"%d\n", costArbore);
        else
        {
            int poz = cautBin(c);
            ++m;
            mcx[m] = x;
            mcy[m] = y;
            costmc[m] = c;
            for (int i = m; i >= poz; --i)
                indicemc[i] = indicemc[i - 1];
            indicemc[poz] = m;
            generareAPM();
            fprintf(fout,"%d\n", costArbore);
        }
    }
    return 0;
}