제출 #1045939

#제출 시각아이디문제언어결과실행 시간메모리
1045939efedmrlr다리 (APIO19_bridges)C++17
100 / 100
2196 ms7748 KiB
    // #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 = 500;
    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();
        }
        
    }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void solve()':
bridges.cpp:156:26: 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]) {
      |                       ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...