Submission #1045763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045763		efedmrlr	Bridges (APIO19_bridges)	C++17	100 / 100	2252 ms	11332 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 = 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();
    }
    
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:156:22: 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