Submission #1198700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198700		hengliao	Bridges (APIO19_bridges)	C++20	14 / 100	2009 ms	30548 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

const ll mxN=2e5+5;
const ll B=500;

struct Edge{
  ll u, v, t1, t2, w;

  bool operator<(const Edge &tar) const{
    return w>tar.w;
  }
};

ll n, m, q;
pll edges[mxN];
ll w[mxN];
ll pret[mxN];
ll flag[mxN];
ll b[mxN], r[mxN], s[mxN], cw[mxN], ans[mxN];
ll dsu[mxN];
vector<array<ll, 6>> v;
vector<array<ll, 4>> roll;

ll ceil_div(ll a, ll b){
  return (a+b-1)/b;
}

void init_dsu(){
  memset(dsu, -1, sizeof(dsu));
}

ll find_set(ll tar){
  if(dsu[tar]<0) return tar;
  return dsu[tar]=find_set(dsu[tar]);
}

ll find_set2(ll tar){
  if(dsu[tar]<0) return tar;
  return find_set(dsu[tar]);
}

void unite(ll a, ll b){
  ll f=find_set(a);
  ll s=find_set(b);
  if(abs(dsu[f]<abs(dsu[s]))) swap(f, s);
  dsu[f]+=dsu[s];
  dsu[s]=f;
}

void unite2(ll a, ll b){
  ll f=find_set2(a);
  ll s=find_set2(b);
  if(abs(dsu[f]<abs(dsu[s]))) swap(f, s);
  roll.pb({f, dsu[f], s, dsu[s]});
  dsu[f]+=dsu[s];
  dsu[s]=f;
}

void roll_back(){
  // assert(!roll.empty());
  dsu[roll.back()[0]]=roll.back()[1];
  dsu[roll.back()[2]]=roll.back()[3];
  roll.pop_back();
}

void solve(){
  cin>>n>>m;
  for(ll i=0;i<m;i++){
    cin>>edges[i].F>>edges[i].S>>w[i];
  }
  cin>>q;
  for(ll i=0;i<q;i++){
    cin>>flag[i];
    pret[i]=0;
    if(flag[i]==1){
      cin>>b[i]>>r[i];
      b[i]--;
    }
    else{
      cin>>s[i]>>cw[i];
    }
  }
  for(ll i=0;i<q;i++){
    if(flag[i]==1){
      ll idx=b[i];
      array<ll, 6> cur={1, edges[idx].F, edges[idx].S, pret[idx], i-1, w[idx]};
      if(cur[3]<=cur[4]) v.pb(cur);
      pret[idx]=i;
      w[idx]=r[i];
    }
  }
  for(ll i=0;i<m;i++){
    array<ll, 6> cur={1, edges[i].F, edges[i].S, pret[i], q, w[i]};
    if(cur[3]<=cur[4]) v.pb(cur);
  }
  for(ll i=0;i<q;i++){
    if(flag[i]==2){
      array<ll, 6> cur={2, 0, 0, i, s[i], cw[i]};
      v.pb(cur);
    }
  }
  auto compare=[&](array<ll, 6> a, array<ll, 6> b){
    if(a[5]!=b[5]) return a[5]>b[5];
    return a[0]<b[0];
  };
  sort(v.begin(), v.end(), compare);
  // for(auto &it:v){
  //   for(ll i=0;i<6;i++){
  //     cout<<it[i]<<' ';
  //   }
  //   cout<<'\n';
  // }
  for(ll bl=0;bl<q/B;bl++){
    vector<array<ll, 6>> tep;
    init_dsu();
    ll low=bl*B;
    ll high=min((bl+1)*B-1, q-1);
    for(auto &it:v){
      if(it[0]==1){
        if(it[3]<low && it[4]>high){
          if(find_set(it[1])!=find_set(it[2])){
            unite(it[1], it[2]);
          }
          
        }
        else if((it[3]>=low && it[3]<=high) || (it[4]>=low && it[4]<=high)){
          tep.pb(it);
        }
      }
      else{
        if(it[3]<low || it[3]>high) continue;
        ll cnt=0;
        // cout<<"dealing "<<it[3]<<'\n';
        for(auto &it2:tep){
          if(it2[3]<=it[3] && it2[4]>=it[3]){
            if(find_set2(it2[1])!=find_set2(it2[2])){
              unite2(it2[1], it2[2]);
              // cout<<"uniting "<<it2[1]<<' '<<it2[2]<<'\n';
              cnt++;
            }
          }
        }
        ll p=find_set2(it[4]);
        ans[it[3]]=abs(dsu[p]);
        while(cnt--){
          roll_back();
        }
      }
    }
  }
  for(ll i=0;i<q;i++){
    if(flag[i]==2){
      cout<<ans[i]<<'\n';
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  solve();

  return 0;
}

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