Submission #561835

#	Time	Username	Problem	Language	Result	Execution time	Memory
561835		Je_O	Bridges (APIO19_bridges)	C++17	100 / 100	2106 ms	151760 KiB

bridges

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int BLOCK = 1000;
int u[M], v[M], w[M];
int t[M], x[M], y[M];
bool cek[M];
vector<int> join[M];
int par[N], sz[N];
int ans[M];

stack<int> stk;

int find(int x){
    while(par[x] != x)x = par[x];
    return x;
}

void merge(int x, int y){
    x = find(x); y = find(y);
    if(x == y)return;
    if(sz[x] > sz[y])swap(x, y);
    stk.push(x);
    par[x] = y;
    sz[y] += sz[x];
    return;
}

void rollback(int s){
    while(stk.size() > s){
        int x = stk.top(); stk.pop();
        sz[par[x]] -= sz[x];
        par[x] = x;
    }
    return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> u[i] >> v[i] >> w[i];
    }
    int q; cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> t[i] >> x[i] >> y[i];
    }
    for(int i = 1; i <= q; i += BLOCK){
        iota(par + 1, par + n + 1, 1);
        fill(sz + 1, sz + n + 1, 1);
        fill(cek + 1, cek + m + 1, false);
        int l = i, r = min(i + BLOCK - 1, q);
        vector<int> pending, ask;
        for(int j = l; j <= r; ++j){
            if(t[j] == 1){
                cek[x[j]] = true;
                pending.pb(j);
            }else{
                ask.pb(j);
            }
        }
        vector<int> lst;
        for(int j = 1; j <= m; ++j){
            if(!cek[j])lst.pb(j);
        }
        for(int j = l; j <= r; ++j){
            if(t[j] == 1){
                w[x[j]] = y[j];
            }else{
                for(int k: pending){
                    if(w[x[k]] >= y[j]){
                        join[j].pb(x[k]);
                    }
                }
            }
        }
        sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
        sort(lst.begin(), lst.end(), [&](int a, int b) { return w[a] > w[b]; });
        int pt = 0;
        for(int j: ask){
            while(pt < lst.size() && w[lst[pt]] >= y[j]){
                merge(u[lst[pt]], v[lst[pt]]);
                ++pt;
            }
            int s = stk.size();
            for(int k: join[j])merge(u[k], v[k]);
            ans[j] = sz[find(x[j])];
            rollback(s);
        }
    }
    for(int i = 1; i <= q; ++i){
        if(t[i] == 2)cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:41:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     while(stk.size() > s){
      |           ~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             while(pt < lst.size() && w[lst[pt]] >= y[j]){
      |                   ~~~^~~~~~~~~~~~

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