Submission #1045946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045946		efedmrlr	Bridges (APIO19_bridges)	C++17	100 / 100	1900 ms	7728 KiB

bridges

        // #pragma GCC optimize("O3,Ofast,unroll-loops")
        // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
        #include <bits/stdc++.h>
         
        using namespace std;
         
         
        #define lli long long int
        #define MP make_pair
        #define pb push_back
        #define REP(i,n) for(int i = 0; (i) < (n); (i)++)
        #define all(x) x.begin(), x.end()
        #define rall(x) x.rbegin(), x.rend()
         
        void fastio() {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
        }
         
         
        const double EPS = 0.00001;
        const int INF = 1e9+500;
        const int N = 1e5+5;
        const int ALPH = 26;
        const int LGN = 25;
        constexpr int MOD = 1e9+7;
        const int B = 600;
        int n,m,q;
        vector<array<int, 3> > edges;
        vector<array<int, 3> > que;
        vector<int> ans(N, -1);
        struct DSU {
            vector<int> p, sz;
            vector<array<int, 3> > rb;
            void real_reset(int s) {
                p.assign(s + 3, 0);
                sz.assign(s + 3, 1);
            }
            void reset(int s) {
                rb.clear();
                for(int i = 1; i <= s; i++) {
                    make_set(i);
                }
            }
            void make_set(int x) {
                p[x] = x;
                sz[x] = 1;
            }
            int find_set(int x) {
                return p[x] == x ? x : find_set(p[x]);
            }
            void union_set(int x, int y) {
                // cout << "connect: " << x << " " << y << "\n";
                x = find_set(x); y = find_set(y);
                if(x == y) {
                    rb.pb({-1, -1});
                    return;
                }
                if(sz[x] > sz[y]) swap(x, y);
                p[x] = y;
                sz[y] += sz[x];
                rb.pb({x, y, sz[x]});
            } 
            void roll() {
                if(!rb.size()) return;
                // cout << "discon: " << rb.back()[0] << " " << rb.back()[1]<< "\n";
                if(rb.back()[0] == -1) {
                    rb.pop_back();
                    return;
                }
         
                auto c = rb.back();
                p[c[0]] = c[0];
                sz[c[0]] = c[2];
                sz[c[1]] -= c[2];
                rb.pop_back(); 
            }
        };
         
        inline void solve() {
            cin>>n>>m;
            edges.pb({0, 0, 0});
            REP(i, m) {
                int a, b, d;
                cin >> a >> b >> d;
                d *= -1;
                edges.pb({a, b, d});
            }
            cin >> q;
            
            REP(z, q) {
                int t;
                cin >> t;
                int a, b;
                cin >> a >> b;
                b *= -1;
                que.pb({t, a, b});
            }
            DSU ds;
            ds.real_reset(n + 1);
            vector<int> st;
            unordered_set<int> forb;
            int op = 0;
            vector<int> ext(m + 2, 0);
            vector<int> curq;
            for(int bat = 0; bat < q; bat+=B) {
                // cout << "bat:" << bat << endl;
                forb.clear();
                st.clear();
                curq.clear();
                int sz = min(B, q - bat);
                ds.reset(n + 1);
                for(int i = 0; i < sz; i++) {
                    if(que[bat + i][0] == 1) {
                        forb.insert(que[bat + i][1]);
                    }
                    else {
                        curq.pb(bat + i);
                    }
                    
                }
                // cout << "forb: ";
                // for(auto c : forb) {
                //     cout << c << " ";
                // }
                // cout << endl;
                for(int i = 1; i <= m; i++) {
                    if(!forb.count(i)) {
                        st.pb(i);
                    }
                }
                while(op < bat) {
                    if(que[op][0] == 1) {
                        edges[que[op][1]][2] = que[op][2];
                    }
                    op++;
                }
                sort(all(st), [&](int x, int y) {
                    return edges[x][2] < edges[y][2];
                });
                for(auto c : forb) {
                    ext[c] = edges[c][2];
                    
                }
                int pt = 0;
                sort(all(curq), [&](int x, int y) {
                    return que[x][2] < que[y][2];
                });
                
                for(auto ind : curq) {
                    for(auto c : forb) {
                    ext[c] = edges[c][2];
                    
                    }
                    // cout << "two pointer: " << endl;
                    while(pt < st.size() && edges[st[pt] ][2] <= que[ind][2]) {
                        ds.union_set(edges[st[pt]][0], edges[st[pt]][1]);
                        pt++;
                    }
                    for(int i = bat; i < ind; i++) {
                        if(que[i][0] == 2) continue;
                        ext[que[i][1]] = que[i][2];
                            
                    }
                    // cout << "sqr\n";
                    int cnt = 0;
                    for(auto c : forb) {
                        if(ext[c] > que[ind][2]) {
                            continue;
                        }
                        // cout << "ext : " << ext[c] << endl;
                        cnt++;
                        ds.union_set(edges[c][0], edges[c][1]);
                    }
         
                    // cout << que[ind][1] << " " << que[ind][2] << " " << que[ind][3] << "\n";  
                    ans[ind] = ds.sz[ds.find_set(que[ind][1])];
                    REP(z, cnt) {
                        ds.roll();
                    }
                }
         
            } 
            REP(i, q) {
                if(ans[i] == -1) continue;
                cout << ans[i] << "\n";
            } 
        }
         
        signed main() {
         
            fastio();
            int test = 1;
            //cin>>test;
            while(test--) {
                solve();
            }
            
        }

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:156:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |                     while(pt < st.size() && edges[st[pt] ][2] <= que[ind][2]) {
      |                           ~~~^~~~~~~~~~~

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