Submission #1128612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128612		tymoniusz	Bridges (APIO19_bridges)	C++17	100 / 100	1733 ms	20476 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 100005;

int W[N];
int W_q[N];
int U[N];
int V[N];
bool blocked[N];
bool vis[N];
vector <int> e[N];
int siz[N];
int par[N];
int res[N];

void dfs(int u, int& res)
{
    res += siz[u];
    vis[u] = true;
    for (int v : e[u])
    {
        if (vis[v]) continue;
        dfs(v, res);
    }
}

int find(int a)
{
    if (par[a] == a) return a;
    return par[a] = find(par[a]);
}

void unite(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b) return;
    par[a] = b;
    siz[b] += siz[a];
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> edges;

    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        W[i] = w;
        V[i] = v;
        U[i] = u;

        edges.pb(i);
    }

    int q;
    cin >> q;

    vector <tuple <int, int, int> > queries;
    vector <tuple <int, int, int> > vec;

    int root = 320;

    for (int i = 1; i <= q; i++)
    {
        int t, a, b;
        cin >> t >> a >> b;

        if (t == 2) queries.pb({b, a, i});
        else
        {
            vec.pb({a, b, i});
            blocked[a] = true;
        }

        if (vec.size() != root && i != q) continue;

        sort(edges.begin(), edges.end(), [](int a, int b)
             {
                 return W[a] > W[b];
             });
        edges.pb(0);
        sort(queries.begin(), queries.end());

        for (int i = 1; i <= n; i++)
        {
            par[i] = i;
            siz[i] = 1;
        }

        for (int ind : edges)
        {
            if (blocked[ind]) continue;
            while (!queries.empty() && get <0> (queries.back()) > W[ind])
            {
                auto [w_q, s, ind_q] = queries.back();
                queries.pop_back();
                for (auto [j, w, id] : vec) W_q[j] = W[j];
                for (auto [j, w, id] : vec)
                {
                    if (id < ind_q) W_q[j] = w;
                }
                for (auto [j, w, id] : vec)
                {
                    if (W_q[j] >= w_q)
                    {
                        int u = find(U[j]), v = find(V[j]);
                        e[u].pb(v);
                        e[v].pb(u);
                    }
                }
                s = find(s);
                dfs(s, res[ind_q]);
                vis[s] = false;
                for (auto [j, w, id] : vec)
                {
                    int u = find(U[j]), v = find(V[j]);
                    e[u].clear();
                    e[v].clear();
                    vis[u] = false;
                    vis[v] = false;
                }

            }
            unite(U[ind], V[ind]);
        }

        for (auto [j, w, id] : vec)
        {
            W[j] = w;
            blocked[j] = false;
        }

        vec.clear();
        queries.clear();
    }

    for (int i = 1; i <= q; i++) if (res[i] != 0) cout << res[i] << "\n";


    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27