Submission #463903

#	Time	Username	Problem	Language	Result	Execution time	Memory
463903		czhang2718	Bridges (APIO19_bridges)	C++14	73 / 100	3031 ms	7236 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 s[100001];
int ans[100001];
stack<int> changes;
int use[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){
    cin >> t[i] >> query[i].f >> query[i].s;
  }

  vi qedge;
  vi qu;

  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);
    qedge.clear();
    qu.clear();
    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);
    }
    edges.clear();
    rep(i, 1, m) if(!skip[i]) edges.pb(i);
    sort(all(qu), byw);
    int k=0;
    if(!qu.empty()) sort(all(edges), cmp);
    for(int i:qu){
      while(k<sz(edges) && edge[edges[k]].f>=query[i].s){
        join(edges[k], 0);
        k++;
      }
      int p=upper_bound(all(qedge), i)-qedge.begin();
      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<sz(qedge); 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]==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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27