Submission #136949

#	Time	Username	Problem	Language	Result	Execution time	Memory
136949		KLPP	Bridges (APIO19_bridges)	C++14	27 / 100	3039 ms	45964 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define BLOCK 10000
int n,m,q;
lld edgelist[1000000][3];
lld queries[1000000][3];
lld answers[1000000];
bool permanent[1000000];
lld save[1000000];
vector<int> nei[1000000];
bool visited[1000000];
class DSU{
  int parent[1000000];
  int size[1000000];
public:
  void init(int N){
    rep(i,0,N){
      parent[i]=i;
      size[i]=1;
    }
  }
  int root(int a){
    if(parent[a]==a)return a;
    parent[a]=root(parent[a]);
    return parent[a];
  }
  void merge(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(size[a]<size[b])swap(a,b);
    size[a]+=size[b];
    parent[b]=a;
  }
  int SZ(int node){
    return size[root(node)];
  }
};
DSU *D;
void process(int l, int r){
  //cout<<l<<" "<<r<<endl;
  rep(i,0,n)visited[i]=false;
  rep(i,0,m){
    permanent[i]=true;
    save[i]=edgelist[i][2];
  }
  vector<int> changed;
  rep(i,l,r){
    if(queries[i][0]==1){
      //cout<<queries[i][1]<<endl;
      permanent[queries[i][1]]=false;
    }
  }
  vector<pii> V;//edges/weights
  rep(i,0,m){
    //cout<<permanent[i]<<endl;
    if(permanent[i]){
      V.push_back(pii(edgelist[i][2],i+1));//peso,numero
    }else changed.push_back(i);
  }
  rep(i,l,r){
    if(queries[i][0]==2){
      V.push_back(pii(queries[i][2],-i));//peso,tempo da query
    }
  }
  sort(V.begin(),V.end());
  reverse(V.begin(),V.end());
  D->init(n);
  trav(a,V){
    
    //cout<<a.first<<" "<<a.second<<endl;
    if(a.second>0){
      int num=a.second-1;
      D->merge(edgelist[num][0],edgelist[num][1]);
    }else{
      int time=-a.second;
      //cout<<queries[time][0]<<endl;
      rep(i,l,time){
	if(queries[i][0]==1){
	  edgelist[queries[i][1]][2]=queries[i][2];
	}
      }
      
      vector<pii> edges;
      trav(b,changed){
	//cout<<b<<"A"<<edgelist[b][2]<<" "<<queries[time][2]<<endl;
	if(edgelist[b][2]>=queries[time][2]){
	  
	  if(D->root(edgelist[b][1])!=D->root(edgelist[b][0])){
	    edges.push_back(pii(D->root(edgelist[b][1]),D->root(edgelist[b][0])));
	  }
	}
      }
      trav(e,edges){
	//cout<<e.first<<" "<<e.second<<endl;
	nei[e.first].push_back(e.second);
	nei[e.second].push_back(e.first);
	visited[e.second]=false;
	visited[e.first]=false;
      }
      //cout<<"S"<<" "<<D->root(queries[time][1])<<" "<<time<<endl;
      queue<int> q;
      q.push(D->root(queries[time][1]));
      visited[D->root(queries[time][1])]=true;
      answers[time]=0;
      stack<int> s;
      while(!q.empty()){
	int u=q.front();
	q.pop();
	answers[time]+=D->SZ(u);
	s.push(u);
	trav(v,nei[u]){
	  if(!visited[v]){
	    visited[v]=true;
	    q.push(v);
	  }
	}
      }
      while(!s.empty()){
	visited[s.top()]=false;
	s.pop();
      }
      trav(e,edges){
	nei[e.first].clear();
	nei[e.second].clear();
	
      }
      trav(b,changed){
	edgelist[b][2]=save[b];
      }
    }
  }
}
int main(){
  D=new DSU();
  scanf("%d %d",&n,&m);
  rep(i,0,m){
    rep(j,0,3){
      scanf("%lld",&edgelist[i][j]);
      if(j<2)edgelist[i][j]--;
    }
  }
  scanf("%d",&q);
  rep(i,0,q){
    rep(j,0,3)scanf("%lld",&queries[i][j]);
    queries[i][1]--;
  }
  rep(i,0,q/BLOCK+1){
    process(BLOCK*i,min(BLOCK*(i+1),q));
    rep(j,BLOCK*i,min(BLOCK*(i+1),q)){
      if(queries[j][0]==1){
	edgelist[queries[i][1]][2]=queries[i][2];
      }
    }
  }
  rep(i,0,q){
    if(queries[i][0]==2){
      printf("%lld\n",answers[i]);
    }
  }
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:144:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld",&edgelist[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
bridges.cpp:150:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     rep(j,0,3)scanf("%lld",&queries[i][j]);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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