Submission #1230215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230215		trimkus	Bridges (APIO19_bridges)	C++20	100 / 100	1538 ms	26408 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> sz, par;
    stack<int> st;
    int n;
    DSU(int n) {
        this->n = n;
        sz = vector<int>(n, 1);
        par = vector<int>(n);
        iota(begin(par), end(par), 0);
    }
    void reset() {
        sz = vector<int>(n, 1);
        par = vector<int>(n);
        iota(begin(par), end(par), 0);
    }
    int get(int x) {
        return par[x] == x ? x : get(par[x]);
    }
    int size(int x) {
        return sz[get(x)];
    }
    void unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        sz[y] += sz[x];
        st.push(x);
        par[x] = par[y];
    }
    void rollback(int t) {
        while (st.size() > t) {
            int x = st.top(); st.pop();
            sz[par[x]] -= sz[x];
            par[x] = x;
        }
    }
};

const int MAXN = 1e5 + 1;
int W[MAXN + 1];
int a[MAXN + 1], b[MAXN + 1];
int t[MAXN + 1], c[MAXN + 1], d[MAXN + 1];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i] >> W[i];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> t[i] >> c[i] >> d[i];
    }
    vector<int> res(q + 1);
    const int jump = 1000;
    DSU dsu(n + 1);
    vector<bool> same(m + 1);
    for (int l = 1; l <= q; l += jump) {
        int r = min(q + 1, l + jump);
        dsu.reset();
        same = vector<bool>(m + 1, true);
        vector<int> upd, quer, left;
        for (int i = l; i < r; ++i) {
            if (t[i] == 1) {
                same[c[i]] = false;
                upd.push_back(i);
            } else quer.push_back(i);
        }
        vector<vector<int>> add(jump);
        for (int i = 1; i <= m; ++i) {
            if (same[i]) {
                left.push_back(i);
            }
        }
        for (int i = l; i < r; ++i) {
            int k = i - l;
            // cerr << c[i] << " " << d[i] << "\n";
            if (t[i] == 1) {
                W[c[i]] = d[i];
            } else {
                for (auto& j : upd) {
                    if (W[c[j]] >= d[i]) {
                        add[k].push_back(c[j]);
                    }
                }
            }
        }
        int ptr = 0;
        sort(begin(quer), end(quer), [&](int x, int y) {
            return d[x] > d[y];
        });
        sort(begin(left), end(left), [&](int x, int y) {
            return W[x] > W[y];
        });
        // for (auto& u : left) {
        //     cerr << u << " ";
        // }
        // cerr << "\n";
        for (auto& i : quer) {
            // cerr << i << "\n";
            while (ptr < (int)left.size() && W[left[ptr]] >= d[i]) {
                dsu.unite(a[left[ptr]], b[left[ptr]]);
                ptr += 1;
            }
            int prv = dsu.st.size();
            int k = i - l;
            for (auto& j : add[k]) {
                dsu.unite(a[j], b[j]);
            }
            res[i] = dsu.size(c[i]);
            dsu.rollback(prv);
        }
    }
    for (int i = 1; i <= q; ++i) {
        if (t[i] == 2) {
            cout << res[i] << "\n";
        }
    }
}

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