Submission #463913

#	Time	Username	Problem	Language	Result	Execution time	Memory
463913		czhang2718	Bridges (APIO19_bridges)	C++14	100 / 100	2943 ms	6756 KiB

bridges

#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size() 
#define f first
#define s second
#define pb push_back
#define nl '\n'
typedef vector<int> vi;
typedef pair<int, int> pii;

const int B=1000;
int n, m, q;
pair<int, pii> edge[100001];
bool t[100001];
pii query[100001];
bool skip[100001];
int par[100001];
int s[100001];
int ans[100001];
stack<int> changes;
int use[100001];
int qedge[100001];
int edges[100001];
int qu[100001];

int find(int x){
  while(x!=par[x]) x=par[x];
  return x;
}

void join(int i, bool ch){
  int a=find(edge[i].s.f);
  int b=find(edge[i].s.s);
  if(a==b) return;
  if(s[a]<s[b]) swap(a, b);
  if(ch) changes.push(b);
  par[b]=a;
  s[a]+=s[b];
}

bool byw(int i, int j){
  return query[i].s>query[j].s;
}

void undo(){
  while(!changes.empty()){
    int x=changes.top(); changes.pop();
    s[par[x]]-=s[x];
    par[x]=x;
  }
}

bool cmp(int i, int j){
  return edge[i].f>edge[j].f;   
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  cin >> n >> m;
  rep(i, 1, m){
    int u, v, w; cin >> u >> v >> w;
    edge[i]={w, {u, v}};
  }

  cin >> q;
  rep(i, 1, q){
    int type;
    cin >> type >> query[i].f >> query[i].s;
    t[i]=type==1;
  }

  rep(b, 0, q/B){  
    rep(i, 1, n) par[i]=i, s[i]=1;
    int l=max(1, B*b);
    int r=min(q, B*(b+1)-1);
    iota(par+1, par+1+n, 1);
    fill(s+1, s+1+n, 1);
    rep(i, 1, m) skip[i]=0, use[i]=0;
    int qedgei=0;
    int qui=0;
    int edgesi=0;
    for(int i=l; i<=r; i++) {
      if(t[i]==1) skip[query[i].f]=1, qedge[qedgei++]=i;
      else qu[qui++]=i;
    }
    rep(i, 1, m) if(!skip[i]) edges[edgesi++]=i;
    sort(qu, qu+qui, byw);
    int k=0;
    sort(edges, edges+edgesi, cmp);
    for(int ind=0; ind<qui; ind++) {
      int i=qu[ind];
      while(k<edgesi && edge[edges[k]].f>=query[i].s){
        join(edges[k], 0);
        k++;
      }
      int p=0;
      while(p<qedgei && qedge[p]<=i) p++;
      for(int l=p-1; l>=0; l--) {
        int j=qedge[l];
        if(query[j].s>=query[i].s && use[query[j].f]!=i) join(query[j].f, 1);
        use[query[j].f]=i;
      }
      
      for(int j=p; j<qedgei; j++) {
        int e=query[qedge[j]].f;
        if(use[e]!=i && edge[e].f>=query[i].s) join(e, 1), use[e]=i;
      }
      ans[i]=s[find(query[i].f)];
      undo();
    }

    rep(i, l, r){
      if(t[i]==1) edge[query[i].f].f=query[i].s;
    }
  }

  rep(i, 1, q) if(!t[i]) cout << ans[i] << nl;
}

// q/B * (2mlogm+B) + q*B*log(m)
// m * sqrt(q) *  logm
// 1e5 * 3e2 * 2e1
// 6e8

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