Submission #821940

#	Time	Username	Problem	Language	Result	Execution time	Memory
821940		smirichto	Bridges (APIO19_bridges)	C++17	59 / 100	3022 ms	78952 KiB

bridges

#include<bits/stdc++.h>
using namespace std ;


// dsu with rollback
int n , q , m ;
const int B = 500 , N = 2e5 + 5 ;
stack<int> stck;
int sz[N], cmp[N];

void reset() {
    iota(cmp + 1, cmp + 1 + n, 1);
    fill(sz + 1, sz + n + 1, 1);
    while (!stck.empty()) stck.pop() ;
}

inline int find(int a) {
    while (cmp[a] != a) a = cmp[a];
    return a;
}

void onion(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    stck.push(a);
    sz[b] += sz[a];
    cmp[a] = cmp[b];
}

void rollback(int x) {
    assert(x>=0) ;
    while (stck.size() > x) {
        int k = stck.top();
        stck.pop();
        sz[cmp[k]] -= sz[k];
        cmp[k] = k;
    }
}


vector<array<int,4>> qr[N];
int ans[N] , typ[N];
int old[N] , changed[N] , u[N] , v[N]  ;
vector<int> bonus[N] ;
void solve(){
    cin>>n>>m ;
    for(int i = 1 ; i<=m ; i++){
        cin>>u[i]>>v[i]>>old[i] ;
    }
    cin>>q ;
    for(int i = 1 ; i<=q ; i++){
        int tp , a , b ;
        cin>>tp>>a>>b ;
        qr[i/B].push_back({tp , a , b , i}) ;
        typ[i] = tp ;
    }

    for(int block = 0 ; block<=q/B ; block++){
        reset() ;
        for(int i = 1 ; i<=m ; i++) changed[i] = 0 ;
        vector<array<int,3>> vec ;
        for(auto a : qr[block]){
            if(a[0]==1){
                changed[a[1]] = 1 ;
                old[a[1]] = a[2] ;
            }
            else{
                vec.push_back({a[2] , a[1] , a[3]}) ;
                bonus[a[3]].clear() ;
                for(auto e : qr[block]){
                    if(e[0]==1 && old[e[1]] >= a[2]){
                        bonus[a[3]].push_back(e[1]) ;
                    }
                }
            }
        }
        vector<array<int,2>> edges ;
        for(int j = 1 ; j<=m ; j++){
            if(changed[j]) continue;
            edges.push_back({old[j] , j}) ;
        }
        sort(edges.rbegin() , edges.rend()) ;
        sort(vec.rbegin() , vec.rend()) ;

        int j = 0 ;

        for(auto & i : vec){
            while(j<edges.size() && edges[j][0]>=i[0]){
                onion(u[edges[j][1]] , v[edges[j][1]]) ;
                ++j ;
            }
            int c = stck.size() ;
            for(auto & e : bonus[i[2]]){
                onion(u[e] , v[e]) ;
            }
            ans[i[2]] = sz[find(i[1])] ;
            rollback(c) ;
        }

    }
    for(int i = 1 ; i<=q ; i++){
        if(typ[i]==1) continue;
        cout<<ans[i]<<endl;
    }
}


int main(){
    ios::sync_with_stdio(false) ; cin.tie(nullptr) ;

    solve() ;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:33:24: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while (stck.size() > x) {
      |            ~~~~~~~~~~~~^~~
bridges.cpp: In function 'void solve()':
bridges.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(j<edges.size() && edges[j][0]>=i[0]){
      |                   ~^~~~~~~~~~~~~

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