Submission #729759

#	Time	Username	Problem	Language	Result	Execution time	Memory
729759		1075508020060209tc	Bridges (APIO19_bridges)	C++14	100 / 100	2949 ms	10032 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
//#define int long long
int n;int m;int Q;
int uf[50005];int sz[50005];

stack<array<int,3>>stk;

void rollback(){
uf[stk.top()[0]]=stk.top()[0];
sz[stk.top()[1]]=stk.top()[2];
stk.pop();
}
int fin(int x){
if(uf[x]==x){return x;}
return fin(uf[x]);
}
void mrg(int a,int b){
//cout<<a<<" "<<b<<endl;
int pa=fin(a);int pb=fin(b);
if(pa==pb){stk.push({0,0,0});return;}
if(sz[pa]<sz[pb]){swap(pa,pb);}
uf[pb]=pa;
sz[pa]+=sz[pb];
stk.push({pb,pa,sz[pa]-sz[pb]});
}
int vis[200005];
void init(){
while(stk.size()){stk.pop(); }
for(int i=1;i<=n;i++){
    uf[i]=i;sz[i]=1;
}
for(int i=1;i<=m;i++){
    vis[i]=0;
}
}

int ar[200005];int br[200005];int cr[200005];
int qt[200005];int qa[200005];int qb[200005];


void adde(vector<pair<int,int>>&es){
    for(int i=1;i<=m;i++){
        if(vis[i]){continue;}
        es.push_back({cr[i],i});
    }
    sort(es.begin(),es.end());
    reverse(es.begin(),es.end());
}
int ans[200005];
int tar[200005];int tbr[200005];int tcr[200005];int rmp[200005];
void relabel(){

vector<pair<int,int>>es;
for(int i=1;i<=m;i++){
    es.push_back({cr[i],i});
}
sort(es.begin(),es.end());
for(int i=0;i<es.size();i++){
    tar[i+1]=ar[es[i].second];
    tbr[i+1]=br[es[i].second];
    tcr[i+1]=es[i].first;
    rmp[es[i].second]=i+1;
}
for(int i=1;i<=Q;i++){
    if(qt[i]==1){
        qa[i]=rmp[qa[i]];
    }
}
for(int i=1;i<=m;i++){
    ar[i]=tar[i];br[i]=tbr[i];cr[i]=tcr[i];
}


}


signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i]>>cr[i];
}
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>qt[i]>>qa[i]>>qb[i];
}
//relabel();
int adq=0;
while(Q%600!=0){
    Q++;adq++;
    qt[Q]=2;qa[Q]=1;qb[Q]=1;
}

int block=600;
int lblc=0;
vector<pair<int,int>>es;
init();
for(int i=1;i<=block;i++){
    if(qt[i]==1){
        vis[qa[i]]=1;
    }
}
adde(es);

for(int q=1;q<=Q;q+=block){
vector<pair<int,int>>qry;
for(int i=q;i<=q+block-1;i++){
    if(qt[i]==2){
        qry.push_back({qb[i],i});
    }
}
sort(qry.begin(),qry.end());reverse(qry.begin(),qry.end());


int eit=0;

for(int i=0;i<qry.size();i++){
    while(eit<es.size()&&es[eit].first>=qry[i].first){mrg(ar[es[eit].second],br[es[eit].second]);eit++;}
    int ecnt=0;
    for(int j=qry[i].second;j>=q;j--){
        if(qt[j]==2){continue;}
        if(vis[qa[j]]==1){
            vis[qa[j]]=2;
            if(qb[j]>=qry[i].first){
                ecnt++;
                mrg(ar[qa[j]],br[qa[j]]);
            }
        }
    }
    for(int j=qry[i].second+1;j<=q+block-1;j++){
        if(qt[j]==2){continue;}
        if(vis[qa[j]]==1){
            vis[qa[j]]=2;
            if(cr[qa[j]]>=qry[i].first){
                ecnt++;
                mrg(ar[qa[j]],br[qa[j]]);
            }
        }
    }
    ans[qry[i].second]=sz[fin(qa[qry[i].second])];
    while(ecnt){rollback();ecnt--;}
    for(int j=q;j<=q+block-1;j++){
        if(qt[j]==1&&vis[qa[j]]==2){vis[qa[j]]=1;}
    }
}





for(int i=q;i<=q+block-1;i++){
    if(qt[i]==1){
        cr[qa[i]]=qb[i];
    }
}

init();
for(int i=q+block;i<=q+block+block-1;i++){
    if(qt[i]==1){
        vis[qa[i]]=1;
    }
}
es.clear();
adde(es);
}

for(int i=1;i<=Q-adq;i++){
    if(qt[i]==2){
        cout<<ans[i]<<endl;
    }
}


}

Compilation message (stderr)

bridges.cpp: In function 'void relabel()':
bridges.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 | for(int i=0;i<es.size();i++){
      |             ~^~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 | for(int i=0;i<qry.size();i++){
      |             ~^~~~~~~~~~~
bridges.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     while(eit<es.size()&&es[eit].first>=qry[i].first){mrg(ar[es[eit].second],br[es[eit].second]);eit++;}
      |           ~~~^~~~~~~~~~
bridges.cpp:98:5: warning: unused variable 'lblc' [-Wunused-variable]
   98 | int lblc=0;
      |     ^~~~

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