Submission #708584

#	Time	Username	Problem	Language	Result	Execution time	Memory
708584		EthanKim8683	Bridges (APIO19_bridges)	C++17	13 / 100	3052 ms	2000 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=50000;
const I M=100000;
tuple<I,I,I>edgs[M];
I inds[M];
I pars[N];
priority_queue<pair<I,I>>ques;
B cmp(I a,I b){
  return edgs[a]>edgs[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 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]={d,u,v};
  }
  I q;cin>>q;
  iota(inds,inds+m,0);
  while(q--){
    I t;cin>>t;
    if(t==1){
      I b,r;cin>>b>>r,b--;
      get<0>(edgs[b])=r;
    }
    if(t==2){
      I s,w;cin>>s>>w,s--;
      sort(inds,inds+m,cmp);
      fill_n(pars,n,-1);
      for(I i=0;i<m;i++){
        I j=inds[i];
        auto[d,u,v]=edgs[j];
        if(d<w)break;
        uni(u,v);
      }
      printf("%i\n",siz(s));
    }
  }
}

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