Submission #821923

#	Time	Username	Problem	Language	Result	Execution time	Memory
821923		smirichto	Bridges (APIO19_bridges)	C++17	14 / 100	979 ms	8172 KiB

bridges

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


// dsu with rollback
int n , q , m ;
const int B = 350 , N = 1e5 + 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>> edges , qr[B];
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 ;
        edges.push_back({w , u , v , i}) ;
        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 ;
    }
    sort(edges.begin() , edges.end()) ;
    reverse(edges.begin() , edges.end()) ;
    for(int block = 0 ; block<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]}) ;
                // time , edges , new_weight
            }
            else{
                vec.push_back({a[2] , a[1] , a[3]}) ;
                // starting_with , starting_node , index
            }
        }
        int j = 0 ;
        sort(vec.begin() , vec.end()) ;
        reverse(vec.begin() , vec.end()) ;

        for(int i = 0 ; i<vec.size() ; i++){
            while(j<edges.size() && edges[j][0]>=vec[i][0]){
                if(changed[edges[j][3]]){
                    ++j ; continue;
                }
                onion(edges[j][1] , edges[j][2]) ;
                ++j ;
            }
            int c = stck.size() ;
            for(int k = 0 ; k<updates.size() ; k++){
                int e = updates[k][1] ;
                int u = endpoints[e].first , v = endpoints[e].second ;
                int w = updates[k][2] ;
                if(updates[k][0]>vec[i][2]){
                    w = old[e] ;
                }
                if(w>=vec[i][0]){
                    onion(u , v) ;
                }
            }
            ans[vec[i][2]] = sz[find(vec[i][1])] ;
            rollback(c) ;
        }
        for(auto a : updates){
            old[a[0]] = 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:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int i = 0 ; i<vec.size() ; i++){
      |                         ~^~~~~~~~~~~
bridges.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while(j<edges.size() && edges[j][0]>=vec[i][0]){
      |                   ~^~~~~~~~~~~~~
bridges.cpp:90:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(int k = 0 ; k<updates.size() ; k++){
      |                             ~^~~~~~~~~~~~~~~

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