Cod sursă (job #676085)

#include <bits/stdc++.h>



using namespace std;



ifstream fin("zapada.in");

ofstream fout("zapada.out");



struct vrajeala

{

    int x, y, c;

    bool operator < (const vrajeala A) const

    {

        return c < A.c;

    }

}a[200005];

vector <vrajeala> ales;

struct DSU

{

    vector <int> t;

    DSU(int n)

    {

        t.resize(n + 5);

    }



    void Union(int x, int y)

    {

        t[x] = y;

    }



    int Find(int x)

    {

        int r = x, y;

        while (t[r])

            r = t[r];



        while (x != r)

        {

            y = t[x];

            t[x] = r;

            x = y;

        }



        return r;

    }

};

int n, m, q;

void Test_Case()

{

    int i, nrcc, x, y, apm = 0, c;

    fin >> n >> m >> q;

    nrcc = n;

    DSU tree(n);

    for (i = 1; i <= m; i++)

        fin >> a[i].x >> a[i].y >> a[i].c;

    sort(a + 1, a + m + 1);

    for (i = 1; i <= m and nrcc > 1; i++)

    {

        x = tree.Find(a[i].x);

        y = tree.Find(a[i].y);

        if (x != y)

        {

            tree.Union(x, y);

            ales.push_back(a[i]);

            nrcc--;

            apm += a[i].c;

        }

    }

    fout << apm << "\n";

    while (q--)

    {

        fin >> x >> y >> c;

        if (c > ales.back().c)

        {

            fout << apm << "\n";

            continue;

        }

        ales.push_back({ x, y, c });

        for (i = ales.size() - 1; i >= 1 and ales[i].c < ales[i - 1].c; i--)

            swap(ales[i], ales[i - 1]);

        DSU tree(n);

        apm = 0;

        nrcc = n;

        for (i = 0; i < ales.size() and nrcc > 1; i++)

        {

            x = tree.Find(ales[i].x);

            y = tree.Find(ales[i].y);

            if (x != y)

            {

                tree.Union(x, y);

                nrcc--;

                apm += ales[i].c;

            }

        }

        fout << apm << "\n";



    }

}



int main()

{

    int t;


    t = 1;

    while (t--)

        Test_Case();



    return 0;

}