Submission #708635

#	Time	Username	Problem	Language	Result	Execution time	Memory
708635		EthanKim8683	Bridges (APIO19_bridges)	C++17	73 / 100	3104 ms	11376 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];
vector<tuple<I,I,I>>upds;
vector<tuple<I,I,I>>qrys;
vector<tuple<I,I,I>>curs;
vector<pair<I,I>>adjs[N];
vector<I>excs;
B cmp(I,I);
set<I,decltype(cmp)*>inds(cmp);
I pars[N];
I ress[Q];
I viss[N];
I tim=1;
I n,m;
B cmp(I a,I b){
  if(d_arr[a]==d_arr[b])return a<b;
  return d_arr[a]>d_arr[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,i]:adjs[a])if(tmps[i]>=w)res+=dfs(b,w);
  return res;
}
void slv(I d){
  curs.clear();
  while(qrys.size()){
    auto[w,s,i]=qrys.back();
    if(w<=d)break;
    qrys.pop_back(),curs.push_back({i,s,w});
  }
  if(curs.empty())return;
  sort(curs.begin(),curs.end());
  for(auto i:excs){
    tmps[i]=d_arr[i];
    auto[u,v]=edgs[i];
    u=fnd(u),v=fnd(v);
    adjs[u].push_back({v,i});
    adjs[v].push_back({u,i});
  }
  auto it=upds.begin();
  for(auto[i,s,w]:curs){
    while(it!=upds.end()){
      auto[j,b,r]=*it;
      if(j>i)break;
      tmps[b]=r,it++;
    }
    ress[i]=dfs(fnd(s),w),tim++;
  }
  for(auto i:excs){
    auto[u,v]=edgs[i];
    u=fnd(u),v=fnd(v);
    adjs[u].clear();
    adjs[v].clear();
  }
}
void bat(){
  sort(excs.begin(),excs.end());
  excs.erase(unique(excs.begin(),excs.end()),excs.end());
  sort(qrys.begin(),qrys.end());
  fill_n(pars,n,-1);
  for(auto i:inds){
    auto[u,v]=edgs[i];
    slv(d_arr[i]),uni(u,v);
  }
  slv(MIN);
  for(auto[i,b,r]:upds)d_arr[b]=r;
  upds.clear(),qrys.clear();
  for(auto i:excs)inds.insert(i);
  excs.clear();
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  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;
    inds.insert(i);
  }
  I q;cin>>q;
  I siz=max(sqrt(log2(m)*m*n/q),1.);
  for(I i=0;i<q;i++){
    I t;cin>>t;
    if(t==1){
      I b,r;cin>>b>>r,b--;
      if(inds.count(b))inds.erase(b);
      upds.push_back({i,b,r});
      excs.push_back(b);
    }
    if(t==2){
      I s,w;cin>>s>>w,s--;
      qrys.push_back({w,s,i});
    }
    if(upds.size()>=siz)bat();
  }
  bat();
  for(I i=0;i<q;i++)if(ress[i])printf("%i\n",ress[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'I main()':
bridges.cpp:115:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'I' {aka 'int'} [-Wsign-compare]
  115 |     if(upds.size()>=siz)bat();
      |        ~~~~~~~~~~~^~~~~

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