Submission #463888

#	Time	Username	Problem	Language	Result	Execution time	Memory
463888		czhang2718	Bridges (APIO19_bridges)	C++14	44 / 100	3072 ms	5320 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];
vi edges;
int t[100001];
pii query[100001];
bool skip[100001];
int par[100001];
int rnk[100001];
int s[100001];
int ans[100001];
vector<vi> changes;
int use[100001];

int find(int x){
  if(par[x]==x) return x;
  return find(par[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(ch) changes.pb({a, rnk[a], s[a], b, rnk[b], s[b]});
  if(rnk[a]<rnk[b]) swap(a, b);
  par[b]=a;
  if(rnk[a]==rnk[b]) rnk[a]++;
  s[a]+=s[b];
}

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

void undo(){
  for(int i=sz(changes)-1; i>=0; i--){
    vi v=changes[i];
    int a=v[0];
    int b=v[3];
    par[a]=a, par[b]=b;
    rnk[a]=v[1], rnk[b]=v[4];
    s[a]=v[2], s[b]=v[5];
  }
  changes.clear();
}

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}};
    edges.pb(i);
  }

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

  rep(b, 0, q/B){
    rep(i, 1, n) par[i]=i, s[i]=1, rnk[i]=0;
    int l=max(1, B*b);
    int r=min(q, B*(b+1)-1);
    vi qedge;
    vi qu;
    rep(i, 1, m) skip[i]=0, use[i]=0;
    for(int i=l; i<=r; i++) {
      if(t[i]==1) skip[query[i].f]=1, qedge.pb(i);
      else qu.pb(i);
    }
    sort(all(qu), byw);
    int k=0;
    if(!qu.empty()) sort(all(edges), cmp);
    for(int i:qu){
      while(k<m && edge[edges[k]].f>=query[i].s){
        if(!skip[edges[k]]) join(edges[k], 0);
        k++;
      }

      for(int j=i-1; j>=l; j--) {
        if(t[j]==2) continue;
        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=sz(qedge)-1; j>=0; j--) {
        if(qedge[j]<i) break;
        int e=query[qedge[j]].f;
        if(use[e]!=i && edge[e].f>=query[i].s) join(e, 1); 
      }
      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]==2) 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: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27