Submission #1010280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010280		RandomUser	Bridges (APIO19_bridges)	C++17	59 / 100	3034 ms	60292 KiB

bridges

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

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

    DSU(int _n) : n(_n+1), comp(_n), 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 (P ? find(par[x]) : par[x] = 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);
        if(P) st.push({ a, b, size[a], size[b] });
        comp--;

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

        return 1;
    }

    void roll(int sz) {
        if(!P) return ;
        while(st.size() > sz) {
            comp++;
            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)]; }
    bool same_set(int a, int b) { return find(a) == find(b); }
    void roll() { if(!st.empty()) roll(st.size() - 1); }
    int snap() { return st.size(); }
};

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;
    vector<array<int, 3> > qus(q);
    for(auto &[t, a, b] : qus) {
        cin >> t >> a >> b;
        if(t == 1) a--;
    }

    const int B = 400;
    vector<int> other[q+1];
    vector<bool> vis(m);
    vector<int> ans(q);
    for(int l=0; l<q; l+=B) {
        DSU<1> dsu(n);
        vector<int> ord;

        for(int i=l; i<=min(q-1, l+B-1); i++) 
            if(qus[i][0] == 1) vis[qus[i][1]] = 1, ord.push_back(qus[i][1]);
        sort(ord.begin(), ord.end());
        ord.erase(unique(ord.begin(), ord.end()), ord.end());

        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);
        }

        vector<int> to_ans;
        for(int i=l; i<=min(q-1, l+B-1); i++)
            if(qus[i][0] == 2) to_ans.push_back(i);

        vector<int> norm;
        for(int i=0; i<m; i++) if(!vis[i]) norm.push_back(i);

        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 function 'int main()':
bridges.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while(p < norm.size() && edges[norm[p]][2] >= qus[id][2]) {
      |                   ~~^~~~~~~~~~~~~
bridges.cpp: In instantiation of 'void DSU<P>::roll(int) [with bool P = true]':
bridges.cpp:121:24:   required from here
bridges.cpp:50: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]
   50 |         while(st.size() > sz) {
      |               ~~~~~~~~~~^~~~

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