Submission #722156

#	Time	Username	Problem	Language	Result	Execution time	Memory
722156		Darren0724	Bridges (APIO19_bridges)	C++17	73 / 100	3077 ms	14072 KiB

bridges

#pragma GCC optimize("Ofast","O4","unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
#define endl '\n'
int K=940;
int n,m;
int pa[50005],sz[50005];
vector<pair<pair<int,int>,pair<int,int>>> rec;
void init(){
    rec.clear();
    for(int i=0;i<n;i++){
        pa[i]=i;
        sz[i]=1;
    }
}
 
int Find(int k){
    return (pa[k]==k?k:Find(pa[k]));
}
void onion(int a,int b){
    a=Find(a);
    b=Find(b);
    //cout<<a<<' '<<b<<endl;
    if(a==b){
        return;
    }
    if(sz[a]>sz[b]){
        swap(a,b);
    }
    //cout<<"onion "<<a<<' '<<b<<endl;
    rec.push_back({{a,pa[a]},{b,sz[b]}});
    pa[a]=b;
    sz[b]+=sz[a];
}
void undo(){
    pair<int,int> a,b;
    tie(a,b)=rec.back();
    rec.pop_back();
    pa[a.fs]=a.sc;
    sz[b.fs]=b.sc;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    vector<int> a(m),b(m),c(m);
    vector<int> g;
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;b[i]--;
        g.push_back(c[i]);
    }
    int q;cin>>q;
    vector<int> id(q),p(q),x(q);
    for(int i=0;i<q;i++){
        cin>>id[i]>>p[i]>>x[i];p[i]--;
        g.push_back(x[i]);
    }
    sort(all(g));
    g.resize(unique(all(g))-g.begin());
 
    int N=g.size();
    for(int i=0;i<m;i++){
        c[i]=lower_bound(all(g),c[i])-g.begin();
    }
    for(int i=0;i<q;i++){
        x[i]=lower_bound(all(g),x[i])-g.begin();
    }
    vector<int> ans(q);
    for(int block=0;block<=q/K;block++){
        vector<int> vis(m);
        int s=K*block;
        int t=K*(block+1);
        t=min(t,q);
        vector<int> idx;
        for(int i=s;i<t;i++){
            if(id[i]==1){
                vis[p[i]]=1;  //modify
            }
            else{
                idx.push_back(i);  //ask
            }
        }
        vector<vector<int>> v(N);
        // no
        for(int i=0;i<m;i++){
            if(vis[i]==0){
                v[c[i]].push_back(i);
            }
        }
        sort(all(idx),[&](int i,int j){return x[i]>x[j];});
        int ptr=N-1; // for add edge
        init();
        for(int j:idx){
            while(ptr>=x[j]){
                for(int k:v[ptr]){
                    onion(a[k],b[k]);
                }
                ptr--;
            }
            int rec1=rec.size();
            for(int i=j;i>=s;i--){
                if(id[i]==2){
                    continue;
                }
                if(vis[p[i]]==1){
                    vis[p[i]]=0;
                    if(x[j]<=x[i]){
                        onion(a[p[i]],b[p[i]]);
                    }
                }
            }
            for(int i=j;i<t;i++){
                if(id[i]==2){
                    continue;
                }
                if(vis[p[i]]==1){
                    vis[p[i]]=0;
                    if(x[j]<=c[p[i]]){
                        onion(a[p[i]],b[p[i]]);
                    }
                }
            }
            for(int i=s;i<t;i++){
                if(id[i]==1){
                    vis[p[i]]=1;
                }
            }
 
            ans[j]=sz[Find(p[j])];
            /*for(int i1=0;i1<n;i1++){
                cout<<pa[i1]<<' ';
            }
            cout<<endl;*/
            while(rec.size()>rec1){
                undo();
            }
        }
        for(int i=s;i<t;i++){
            if(id[i]==1){
                c[p[i]]=x[i];
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]!=0){
            cout<<ans[i]<<endl;
        }
    }
 
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:139:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |             while(rec.size()>rec1){
      |                   ~~~~~~~~~~^~~~~

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