marcosoltecn.cpp

#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int MAXN = 1e5 + 10;

int pai[MAXN], sz[MAXN];
set<pair<int,pair<int,int>>> edges;

//guarda as arestas e gadgets em uso (ativos)
multiset<int> mst;

//guarda as arestas e gadgets que não estão em uso
multiset<int> reserva;

//find do union find
int find(int v)
{
    if(pai[v] == v) return v;
    return pai[v] = find(pai[v]);
}

//une do union find
bool un(pair<int,int> x)
{
    int a = x.ff, b = x.ss;
    a = find(a);
    b = find(b);

    if(a == b) return false;

    if(sz[a] < sz[b]) swap(a,b);

    pai[b] = a;
    sz[a] += sz[b];
    return true;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n,m,k,q; cin >> n >> m >> k >> q;

    for(int i = 1; i <= n; i++) {sz[i] = 1; pai[i] = i;}

    //lê as arestas
    for(int i = 0; i < m; i++)
    {
        int a,b,w; cin >> a >> b >> w;
        edges.insert({w,{a,b}});
    }

    //determina as arestas que estão na MST
    int sum = 0;
    while(!edges.empty())
    {
        auto cur = *edges.begin();

        if(un(cur.ss)) {mst.insert(cur.ff); sum += cur.ff;}
        edges.erase(edges.begin());
    }

    //processa os gadgets
    for(int i = 0; i < k; i++)
    {
        int cur; cin >> cur;
        //se o gadget novo não estiver entre os n-1 menores, coloco ele na reserva
        if(cur > *(--mst.end())) reserva.insert(cur);
        else
        {
            //se ele estiver entre os n-1 menores, coloco ele no grafo
            sum += cur;
            mst.insert(cur);

            //também preciso tirar a aresta de maior peso que está em uso e colocá-la na reserva
            reserva.insert(*(--mst.end()));
            sum -= *(--mst.end());
            mst.erase(--mst.end());
        }
    }

    //processo as queries
    cout << sum << "\n";
    for(int i = 0; i < q; i++)
    {
        int type; cin >> type;

        if(type == 1)
        {
            //processo o gadget novo igual processei os k que estavam disponíveis inicialmente
            int cur; cin >> cur;
            if(cur > *(--mst.end())) reserva.insert(cur);
            else
            {
                sum += cur;
                sum -= *(--mst.end());

                mst.insert(cur);

                reserva.insert(*(--mst.end()));
                mst.erase(--mst.end());
            }
        }
        else
        {
            //como podemos tratar tanto a fibra ótica quanto os gadgets como a mesma coisa
            //eu posso só checar se o gadget que estou tirando está entre os n-1 menores ou não
            int cur; cin >> cur;

            // se ele não estiver dentre os n-1 menores, está na reserva, então tiro de lá
            if(cur > *(--mst.end())) reserva.erase(reserva.find(cur));
            else
            {
                //se ele estiver dentre os n-1 menores, eu tiro da lista de arestas ativas
                sum -= cur;
                mst.erase(mst.find(cur));

                //como retirei uma aresta, preciso repor com uma aresta da reserva
                sum += *reserva.begin();
                mst.insert(*reserva.begin());
                reserva.erase(reserva.begin());
            }
        }
        cout << sum << "\n";
    }
}