Submission #729737

#	Time	Username	Problem	Language	Result	Execution time	Memory
729737		1075508020060209tc	Bridges (APIO19_bridges)	C++14	0 / 100	3035 ms	10464 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){return;}
if(sz[pa]<sz[pb]){stk.push({0,0,0}); 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];
signed main(){

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];
}
int block=320;
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;i++){
    if(qt[i]==2){
        cout<<ans[i]<<endl;
    }
}


}

Compilation message (stderr)

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

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