Submission #965060

#	Time	Username	Problem	Language	Result	Execution time	Memory
965060		steveonalex	Bridges (APIO19_bridges)	C++17	100 / 100	1981 ms	19416 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct DSU{
    int n;
    vector<int> parent, sz;
    bool flag;
    vector<pair<int, int>> history;

    DSU(int _n){
        n = _n;
        parent.resize(n+1); sz.resize(n+1, 1);
        for(int i= 1; i<=n; ++i) parent[i] = i;
        flag = 0;
    }

    int find_set(int u){
        if (u == parent[u]) return u;
        if (flag) return find_set(parent[u]);
        else return parent[u] = find_set(parent[u]);
    }

    bool same_set(int u, int v){return find_set(u) == find_set(v);}
    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) swap(u, v);
            parent[v] = u;
            sz[u] += sz[v];
            if (flag) history.push_back({u, v});
            return true;
        }
        return false;
    }

    int get_size(int u){return sz[find_set(u)];}

    void toggle(){flag = !flag;}
    int get_version(){return history.size();}
    void roll_back(int version){
        while(history.size() > version){
            int u = history.back().first, v = history.back().second;
            history.pop_back();
            parent[v] = v;
            sz[u] -= sz[v];
        }
    }
};

const int N = 1e5 + 69;
const int BLOCK = 350;

int n, m;
array<int, 3> edge[N];
array<int, 3> queries[N];
bool check[N];

vector<array<int, 3>> sweep[N * 2];
int ans[N];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 1; i<=m; ++i) cin >> edge[i][0] >> edge[i][1] >> edge[i][2];

    int q; cin >> q;
    for(int i = 1; i<=q; ++i){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    vector<int> b;
    for(int i= 1; i<=m; ++i) b.push_back(edge[i][2]);
    for(int i= 1; i<=q; ++i) b.push_back(queries[i][2]);

    remove_dup(b);

    for(int i = 1; i<=m; ++i) edge[i][2] = lower_bound(ALL(b), edge[i][2]) - b.begin();
    for(int i = 1; i<=q; ++i) queries[i][2]= lower_bound(ALL(b), queries[i][2]) - b.begin();

    for(int t= 1; t <= q; t += BLOCK){
        int l = t, r = min(t + BLOCK - 1, q);

        vector<int> ligma;
        for(int i= l; i<=r; ++i){
            if (queries[i][0] == 1 && !check[queries[i][1]]){
                check[queries[i][1]] = true;
                ligma.push_back(queries[i][1]);
            }
        }

        DSU mst(n);
        for(int i = b.size(); i>=0; --i) sweep[i].clear();
        for(int i = 1; i<=m; ++i) if (!check[i]){
            sweep[edge[i][2]].push_back({{0,edge[i][0], edge[i][1]}});
        }

        for(int i = l; i<=r; ++i) if (queries[i][0] == 2){
            sweep[queries[i][2]].push_back({{i,queries[i][1], queries[i][2]}});
        }

        for(int i = b.size(); i>=0; --i){
            for(array<int, 3> j: sweep[i]){
                if (j[0] == 0){
                    mst.join_set(j[1], j[2]);
                }
                else{
                    for(int k: ligma) mst.same_set(edge[k][0], edge[k][1]);
                    mst.toggle();
                    int cur = mst.get_version();
                    for(int k = l; k <= j[0]; ++k){
                        if (queries[k][0] == 1){
                            int e = queries[k][1];
                            swap(edge[e][2], queries[k][2]);
                        }
                    }

                    for(int k: ligma) {
                        if (edge[k][2] >= i) mst.join_set(edge[k][0], edge[k][1]);
                    }

                    ans[j[0]] = mst.get_size(j[1]);
                    mst.roll_back(cur);

                    mst.toggle();

                    for(int k = j[0]; k >= l; --k){
                        if (queries[k][0] == 1){
                            int e = queries[k][1];
                            swap(edge[e][2], queries[k][2]);
                        }
                    }
                }
            }
        }

        for(int i= l; i<=r; ++i){
            if (queries[i][0] == 1){
                int e = queries[i][1];
                check[e] = false;
                edge[e][2] = queries[i][2];
            }
        }
    }

    for(int i = 1; i<=q; ++i) if (queries[i][0] == 2) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:83:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         while(history.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