제출 #722174

#제출 시각아이디문제언어결과실행 시간메모리
722174Darren0724Bridges (APIO19_bridges)C++17
59 / 100
3098 ms14676 KiB
#pragma GCC optimize("Ofast","O4","unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")
#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=1100;
int n,m;
int pa[50005],sz[50005];
vector<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.emplace_back(a,b);
    pa[a]=b;
    sz[b]+=sz[a];
}
void undo(){
    int a,b;
    tie(a,b)=rec.back();
    rec.pop_back();
    sz[b]-=sz[a];
    pa[a]=a;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    rec.reserve(7777714);
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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