Cod sursă (job #706840)

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#define nmax 10005
using namespace std;
ifstream in("zapada.in");
ofstream out("zapada.out");

struct muchie
{
    int a, b, c;
    muchie(int a = 0, int b = 0, int c = 0)
    {
        this->a = a;
        this->b = b;
        this->c = c;
    }
    bool operator<(const muchie other)
    {
        return c < other.c;
    }
    void output()
    {
        cout << a << ' ' << b << ' ' << c << '\n';
    }
    bool operator==(const muchie other)
    {
        return a == other.a && b == other.b && c == other.c;
    }
} muchii[10 * nmax];

muchie maxim(const muchie a, const muchie b)
{
    if (a.c < b.c)
        return b;
    return a;
}

int f[nmax * 2];
int h[nmax * 2];

int getroot(int nod)
{
    if (!f[nod])
        return nod;
    int tmp = getroot(f[nod]);
    f[nod] = tmp;
    return tmp;
}

void mergee(int a, int b)
{
    if (h[a] > h[b])
    {
        f[getroot(b)] = getroot(a);
    }
    else
    {
        f[getroot(a)] = getroot(b);
        h[getroot(b)] += (h[getroot(b)] == h[getroot(a)]);
    }
}

struct node
{
    vector<pair<int, int>> adj;
    void rem(int nod, int cost)
    {
        for (auto it = adj.begin(); it != adj.end(); it++)
        {
            if ((*it).first == nod && (*it).second == cost)
            {
                adj.erase(it);
                return;
            }
        }
    }
} nodes[nmax];

muchie r;
bool gasit = 0;

void dfs(int nod, int target, muchie maxx, int d)
{
    if (nod == target)
    {
        r = maxx;
        gasit = 1;
        return;
    }
    for (auto i : nodes[nod].adj)
    {
        if (!gasit && i.first != d)
        {
            dfs(i.first, target, maxim(maxx, muchie(nod, i.first, i.second)), nod);
        }
    }
}

void add(muchie a)
{
    nodes[a.a].adj.push_back({a.b, a.c});
    nodes[a.b].adj.push_back({a.a, a.c});
}

void rem(muchie a)
{
    nodes[a.a].rem(a.b, a.c);
    nodes[a.b].rem(a.a, a.c);
}

int main()
{
    int n, m, k;
    in >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        f[i] = i + n;
    }

    int cost = 0;

    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        muchii[i] = muchie(x, y, c);
    }

    sort(muchii, muchii + m);

    for (int i = 0; i < m; i++)
    {
        if (getroot(muchii[i].a) != getroot(muchii[i].b))
        {
            mergee(muchii[i].a, muchii[i].b);
            cost += muchii[i].c;
            nodes[muchii[i].a].adj.push_back({muchii[i].b, muchii[i].c});
            nodes[muchii[i].b].adj.push_back({muchii[i].a, muchii[i].c});
        }
    }

    out << cost << '\n';

    for (int i = 0; i < k; i++)
    {
        int a, b, c;
        in >> a >> b >> c;
        cost += c;
        gasit = 0;
        muchie ttmp = muchie(a, b, c);
        dfs(a, b, ttmp, -1);
        muchie tmp = r;
        cost -= tmp.c;
        if (!(ttmp == tmp))
        {
            rem(tmp);
            add(ttmp);
        }
        out << cost << '\n';
    }
}