Submission #710645

#	Time	Username	Problem	Language	Result	Execution time	Memory
710645		DennisTran	Bridges (APIO19_bridges)	C++17	100 / 100	2558 ms	8724 KiB

bridges

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }

const int MAXN = 1e5 + 5;
int nBlock = 1005;

int N, M, Q, ans[MAXN];
struct Edge{
    int u, v, w;
} e[2 * MAXN];

struct DSU_roll_back{
    vector <int> lab, rnk;
    stack <int> dsu_save;

    DSU_roll_back() {};
    DSU_roll_back(int _n) {
        lab.assign(_n + 1, 0);
        iota(lab.begin(), lab.end(), 0);
        rnk.assign(_n + 1, 1);
    }

    int get(int u) {return lab[u] == u ? u : get(lab[u]);}
    bool merge(int u, int v) {
        if ((u = get(u)) == (v = get(v))) return false;
        if (rnk[u] < rnk[v]) swap(u, v);
        rnk[u] += rnk[v];
        dsu_save.push(v);
        return lab[v] = u, true;
    }

    int data() {return dsu_save.size();}
    void roll_back(int version) {
        while (dsu_save.size() > version) {
            int u = dsu_save.top(); dsu_save.pop();
            rnk[lab[u]] -= rnk[u];
            lab[u] = u;
        }
    }
};

bool current_change[MAXN];

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    FOR(i, 1, M) cin >> e[i].u >> e[i].v >> e[i].w;
    cin >> Q;
    FOR(i, 1, Q) cin >> e[i + M].u >> e[i + M].v >> e[i + M].w;


    for (int l = 1; l <= Q; l += nBlock) {
        int r = min(Q, l + nBlock - 1);
        vector <int> queries;
        vector <int> changed;
        FOR(i, l, r) {
            if (e[i + M].u == 1) {
                changed.emplace_back(i);
                current_change[e[i + M].v] = true;
            }

            else {
                queries.emplace_back(i + M);
            }
        }

        FOR(i, 1, M) {
            if (current_change[i] == false) {
                queries.emplace_back(i);
            } else current_change[i] = false;
        }
        sort(ALL(queries), [&] (int x, int y) {
             if (e[x].w != e[y].w) return e[x].w > e[y].w;
             return x < y;
        });
        reverse(ALL(changed));

        DSU_roll_back ds(N);
        for (int x : queries) {
            if (x <= M) {
                ds.merge(e[x].u, e[x].v);
            }

            else {
                int ver = ds.data();
                for (int y : changed) if (y <= x - M) {
                    int id = e[y + M].v;
                    if (current_change[id] == false) {
                        current_change[id] = true;
                        if (e[y + M].w >= e[x].w) {
                            ds.merge(e[id].u, e[id].v);
                        }
                    }
                }
                for (int y : changed) if (y > x - M) {
                    int id = e[y + M].v;
                    if (current_change[id] == true) continue;
                    if (e[id].w >= e[x].w) ds.merge(e[id].u, e[id].v);
                }
                ans[x - M] = ds.rnk[ds.get(e[x].v)];
                ds.roll_back(ver);
                for (int y : changed) if (y <= x - M) {
                    int id = e[y + M].v;
                    current_change[id] = false;
                }
            }
        }


        FOR(i, l, r) if (e[i + M].u == 1) {
            int id = e[i + M].v;
            e[id].w = e[i + M].w;
        }
    }

    FOR(i, 1, Q) if (e[i + M].u == 2)
        cout << ans[i] << '\n';
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU_roll_back::roll_back(int)':
bridges.cpp:45:32: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         while (dsu_save.size() > version) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~

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