Submission #1027940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027940		Vanio	Bridges (APIO19_bridges)	C++17	100 / 100	1695 ms	9484 KiB

bridges

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


int par[100001],sz[100001];
stack<int> srb;
int findPar(int k){
    if(par[k]==k) return k;
    return findPar(par[k]);
}
void merg(int a, int b, bool F){
    a=findPar(a);
    b=findPar(b);
    if(a==b) return;
    if(sz[a]>sz[b]) swap(a,b);
    if(F) srb.push(a);
    par[a]=b;
    sz[b]+=sz[a];
}
void rollBack(){
    int k;
    while(!srb.empty()){
        k=srb.top();
        sz[par[k]]-=sz[k];
        par[k]=k;
        srb.pop();
    }
}


struct edg{
    int p,q,w;
};
edg edge[100001];
bool fff2(int x, int y){
    return edge[x].w>edge[y].w;
}


struct query{
    int t,e,nw,s,w,indx;
};
query qr[100001];
bool fff1(int x, int y){
    return qr[x].w>qr[y].w;
}


int n,m,q,ans[100001];
bool f[100001];
vector<int> changed,unchanged,cqs;


int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int i;
cin>>n>>m;
for(i=1;i<=m;i++) cin>>edge[i].p>>edge[i].q>>edge[i].w;

cin>>q;
int qbsz=1000,qbbr,qbStart,qbEnd,j;
qbbr=q/qbsz;
if(q%qbsz>0) qbbr++;

for(j=0;j<qbbr;j++){
    qbStart=j*qbsz+1;
    qbEnd=min((j+1)*qbsz,q);
    changed.clear();
    unchanged.clear();
    cqs.clear();
    for(i=1;i<=m;i++) f[i]=0;
    for(i=1;i<=n;i++){par[i]=i; sz[i]=1;}

    for(i=qbStart;i<=qbEnd;i++){
        cin>>qr[i].t;
        qr[i].indx=i;
        if(qr[i].t==1){
            cin>>qr[i].e>>qr[i].nw;
            f[qr[i].e]=1;
        }
        else{
            cin>>qr[i].s>>qr[i].w;
            cqs.push_back(i);
        }
    }
    for(i=1;i<=m;i++){
        if(f[i]==1) changed.push_back(i);
        else unchanged.push_back(i);
    }
    sort(cqs.begin(),cqs.end(),fff1);
    sort(unchanged.begin(),unchanged.end(),fff2);
    /*for(int ch : unchanged) cout<<ch<<" ";
    cout<<endl;*/

    int eindx=0;
    for(int tq : cqs){
        //cout<<tq<<endl;
        if(eindx<unchanged.size()) while(edge[unchanged[eindx]].w>=qr[tq].w){
            merg(edge[unchanged[eindx]].p,edge[unchanged[eindx]].q,0);
            eindx++;
            if(eindx==unchanged.size()) break;
        }
        for(i=qbStart;i<qr[tq].indx;i++){
            if(qr[i].t==1) swap(qr[i].nw,edge[qr[i].e].w);
        }
        for(int ed : changed) if(edge[ed].w>=qr[tq].w) merg(edge[ed].p,edge[ed].q,1);
        //for(i=1;i<=n;i++) cout<<i<<" "<<par[i]<<" "<<sz[i]<<endl;
        //cout<<sz[findPar(qr[tq].s)]<<'\n'<<endl;;
        ans[qr[tq].indx]=sz[findPar(qr[tq].s)];
        rollBack();
        //for(i=1;i<=n;i++) cout<<i<<" "<<par[i]<<" "<<sz[i]<<endl;
        for(i=qr[tq].indx-1;i>=qbStart;i--){
            if(qr[i].t==1) swap(qr[i].nw,edge[qr[i].e].w);
        }
    }
    for(i=qbStart;i<=qbEnd;i++) if(ans[i]!=0) cout<<ans[i]<<'\n';
    for(i=qbStart;i<=qbEnd;i++){
        if(qr[i].t==1) swap(qr[i].nw,edge[qr[i].e].w);
    }
}







return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(eindx<unchanged.size()) while(edge[unchanged[eindx]].w>=qr[tq].w){
      |            ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             if(eindx==unchanged.size()) break;
      |                ~~~~~^~~~~~~~~~~~~~~~~~

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