제출 #721734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721734		Darren0724	다리 (APIO19_bridges)	C++17	44 / 100	3037 ms	19404 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'
const int K=1500;
int n,m;
vector<int> pa,sz;
vector<pair<pair<int,int>,pair<int,int>>> rec;
void init(){
    pa.clear();
    sz.clear();
    pa.resize(n);
    sz.assign(n,1);
    vector<pair<pair<int,int>,pair<int,int>>>().swap(rec);
    for(int i=0;i<n;i++){
        pa[i]=i;
    }
}

int Find(int k,int p){
    if(pa[k]==k){
        return k;
    }
    assert(p<20);
    return Find(pa[k],p+1);
}
int Find(int k){
    return Find(k,0);
}
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;
        vector<vector<int>> v1(N);
        for(int i=s;i<t;i++){
            if(id[i]==1){
                vis[p[i]]=1;  //modify
            }
            else{
                v1[x[i]].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);
            }
        }
        for(int i=N-1;i>=0;i--){
            for(int j:v1[i]){
                idx.push_back(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:152: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]
  152 |             while(rec.size()>rec1){
      |                   ~~~~~~~~~~^~~~~

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