Submission #821932

#TimeUsernameProblemLanguageResultExecution timeMemory
821932smirichtoBridges (APIO19_bridges)C++17
14 / 100
2896 ms12532 KiB
#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];
pair<int,int> endpoints[N] ;
int old[N] , changed[N] ;
void solve(){
    cin>>n>>m ;
    for(int i = 1 ; i<=m ; i++){
        int u , v , w ; cin>>u>>v>>w ;
        endpoints[i] = make_pair(u , v) ;
        old[i] = w ;
    }
    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() ;
        vector<array<int,3>> vec , updates ;
        for(auto a : qr[block]){
            if(a[0]==1){
                changed[a[1]] = 1 ;
                updates.push_back({a[3] , a[1] , a[2]}) ;
            }
            else{
                vec.push_back({a[2] , a[1] , a[3]}) ;
            }
        }
        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(endpoints[edges[j][1]].first , endpoints[edges[j][1]].second) ;
                ++j ;
            }
            int c = stck.size() ;
            for(auto & update : updates){
                int e = update[1] ;
                int u = endpoints[e].first , v = endpoints[e].second ;
                int w = update[2] ;
                if(update[0]>i[2]){
                    w = old[e] ;
                }
                if(w>=i[0]){
                    onion(u , v) ;
                }
            }
            ans[i[2]] = sz[find(i[1])] ;
            rollback(c) ;
        }
        for(auto a : updates){
            old[a[1]] = a[2] ;
            changed[a[1]] = 0 ;
        }
    }
    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:84: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]
   84 |             while(j<edges.size() && edges[j][0]>=i[0]){
      |                   ~^~~~~~~~~~~~~
#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...