Submission #708541

#	Time	Username	Problem	Language	Result	Execution time	Memory
708541		EthanKim8683	Bridges (APIO19_bridges)	C++17	0 / 100	3028 ms	5044 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=50000;
const I M=100000;
const I Q=100000;
const I MIN=-1e9;
pair<I,I>edgs[M];
I d_arr[M];
I tmps[M];
tuple<I,I,I>qrys[Q];
I pars[N];
I inds[M];
I ress[Q];
set<I>acts;
priority_queue<pair<I,I>>ques;
map<I,map<I,I>>adjs;
I viss[N];
I tim=1;
B cmp(I a,I b){
  return tmps[a]>tmps[b];
}
I fnd(I i){
  return pars[i]<0?i:fnd(pars[i]);
}
void uni(I a,I b){
  if((a=fnd(a))==(b=fnd(b)))return;
  if(pars[a]>pars[b])swap(a,b);
  pars[a]+=pars[b],pars[b]=a;
}
I siz(I i){
  return-pars[fnd(i)];
}
I dfs(I a,I w){
  if(viss[a]==tim)return 0;
  viss[a]=tim;
  I res=siz(a);
  for(auto[b,r]:adjs[a])if(r>=w)res+=dfs(b,w);
  return res;
}
void slv(I d){
  while(ques.size()&&ques.top().first>d){
    I i=ques.top().second;ques.pop();
    auto[t,s,w]=qrys[i];
    adjs.clear();
    for(auto j:acts){
      auto[u,v]=edgs[j];
      u=fnd(u),v=fnd(v);
      if(u==v)continue;
      adjs[u][v]=adjs[v][u]=d_arr[j];
    }
    for(I j=0;j<i;j++){
      auto[t,b,r]=qrys[j];
      if(t!=1)continue;
      auto[u,v]=edgs[b];
      u=fnd(u),v=fnd(v);
      if(u==v)continue;
      adjs[u][v]=adjs[v][u]=r;
    }
    ress[i]=dfs(fnd(s),w),tim++;
  }
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  for(I i=0;i<m;i++){
    I u,v,d;cin>>u>>v>>d,u--,v--;
    edgs[i]={u,v};
    d_arr[i]=d;
  }
  I q;cin>>q;
  I siz=sqrt(q);
  iota(inds,inds+m,0);
  for(I i=0;i<(q+siz-1)/siz;i++){
    I upp=min(siz,q-i*siz);
    acts.clear();
    copy_n(d_arr,m,tmps);
    for(I j=0;j<upp;j++){
      I t;cin>>t;
      if(t==1){
        I b,r;cin>>b>>r,b--;
        qrys[j]={1,b,r};
        tmps[b]=MIN;
        acts.insert(b);
      }
      if(t==2){
        I s,w;cin>>s>>w,s--;
        qrys[j]={2,s,w};
        ques.push({w,j});
      }
    }
    sort(inds,inds+m,cmp);
    fill_n(pars,n,-1);
    for(I j=0;j<m;j++){
      I k=inds[j];
      slv(tmps[k]);
      auto[u,v]=edgs[k];
      uni(u,v);
    }
    slv(MIN);
    for(I j=0;j<upp;j++){
      auto[t,b,r]=qrys[j];
      if(t==1)d_arr[b]=r;
      if(t==2)printf("%i\n",ress[j]);
    }
  }
}

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