Submission #1010295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010295		RandomUser	Bridges (APIO19_bridges)	C++17	73 / 100	3058 ms	57448 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

using ll = long long;

struct DSU {
    int n;
    vector<int> par, size;
    stack<array<int, 4> > st;

    DSU(int _n) : n(_n+1), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

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

    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return 0;
        if(size[a] < size[b]) swap(a, b);
        st.push({ a, b, size[a], size[b] });

        par[b] = a;
        size[a] += size[b];

        return 1;
    }

    void roll(int sz) {
        while(st.size() > sz) {
            for(int i=0; i<2; i++) {
                par[st.top().at(i)] = st.top().at(i);
                size[st.top().at(i)] = st.top().at(i+2);
            }
            st.pop();
        }
    }

    int getSize(int a) { return size[find(a)]; }
    int snap() { return st.size(); }

    void reset() {
        while(!st.empty()) st.pop();
        for(int i=1; i<=n; i++) size[i] = 1, par[i] = i;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

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

    vector<array<int, 3> > edges(m);
    for(auto &[a, b, w] : edges) cin >> a >> b >> w;

    cin >> q;
    int cnt = 0;
    vector<array<int, 3> > qus(q);
    for(auto &[t, a, b] : qus) {
        cin >> t >> a >> b;
        if(t == 1) a--;
        else cnt++;
    }

    int B = sqrt(q) + 20;
    if(cnt == q) B = q;
    vector<int> other[q+1];
    vector<bool> vis(m);
    vector<int> ans(q);
    DSU dsu(n);
    for(int l=0; l<q; l+=B) {
        dsu.reset();
        vector<int> ord, to_ans, norm;

        for(int i=l; i<=min(q-1, l+B-1); i++) {
            if(qus[i][0] == 1) vis[qus[i][1]] = 1;
            else to_ans.push_back(i);
        }

        for(int i=0; i<m; i++) {
            if(vis[i]) ord.push_back(i);
            else norm.push_back(i);
        }

        for(int i=l; i<=min(q-1, l+B-1); i++) {
            if(qus[i][0] == 1) edges[qus[i][1]][2] = qus[i][2];
            else for(int &id : ord) if(edges[id][2] >= qus[i][2]) other[i].push_back(id);
        }

        sort(norm.begin(), norm.end(), [&](int a, int b) { return edges[a][2] > edges[b][2]; });
        sort(to_ans.begin(), to_ans.end(), [&](int a, int b) { return qus[a][2] > qus[b][2]; });

        int p = 0;
        for(int &id : to_ans) {
            while(p < norm.size() && edges[norm[p]][2] >= qus[id][2]) {
                dsu.uni(edges[norm[p]][0], edges[norm[p]][1]);
                p++;
            }

            int ss = dsu.snap();
            for(auto &pos : other[id]) dsu.uni(edges[pos][0], edges[pos][1]);
            ans[id] = dsu.getSize(qus[id][1]);
            dsu.roll(ss);
        }
        for(int i=0; i<m; i++) vis[i] = 0;
    }

    for(int i=0; i<q; i++) if(qus[i][0] == 2) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::roll(int)':
bridges.cpp:36:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while(st.size() > sz) {
      |               ~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             while(p < norm.size() && edges[norm[p]][2] >= qus[id][2]) {
      |                   ~~^~~~~~~~~~~~~

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