Submission #1027085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027085		Vanio	Bridges (APIO19_bridges)	C++17	0 / 100	3043 ms	5712 KiB

bridges

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


int par[100001],sz[100001];
stack<pair<int,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,b});
    par[a]=b;
    sz[b]+=sz[a];
}
void rollBack(){
    while(!srb.empty()){
        auto k=srb.top();
        sz[k.second]-=sz[k.first];
        par[k.first]=k.first;
        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;
for(i=1;i<=q;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;*/
for(i=1;i<=n;i++){par[i]=i; sz[i]=1;}

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=qr[tq].indx-1;i>=1;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>=1;i--){
        if(qr[i].t==1) swap(qr[i].nw,edge[qr[i].e].w);
    }
}
for(i=1;i<=q;i++) if(ans[i]!=0) cout<<ans[i]<<'\n';






return 0;
}

Compilation message (stderr)

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

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