Submission #748586

#	Time	Username	Problem	Language	Result	Execution time	Memory
748586		NeroZein	Bridges (APIO19_bridges)	C++17	100 / 100	1883 ms	12184 KiB

bridges

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int B = 1003;
const int N = 50004;
const int Q = 100005;

stack<int> stk; 
int p[N], sz[N]; 

inline int get (int v) {
  while (p[v] != v) v = p[v];
  return v;
}

inline void unite (int u, int v) {
  u = get(u); v = get(v);
  if (u == v) return;
  if (sz[u] > sz[v]) swap(u, v); 
  sz[v] += sz[u];
  p[u] = v; 
  stk.push(u); 
}

inline void rollback (int time) {
  while (time < (int) stk.size()) {
    int u = stk.top();
    stk.pop(); 
    sz[p[u]] -= sz[u];
    p[u] = u; 
  }
}

int n, m;
int ans[Q]; 
bitset<Q> changed; 
int u[Q], v[Q], d[Q]; 
int t[Q], x[Q], y[Q]; 
vector<int> to_join[B];

void reset () {
  for (int i = 1; i <= n; ++i) {
    p[i] = i; sz[i] = 1; 
  }
  changed.reset(); 
  while (stk.size()) stk.pop(); 
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> u[i] >> v[i] >> d[i]; 
  }
  int q;
  cin >> q; 
  for (int i = 1; i <= q; ++i) {
    cin >> t[i] >> x[i] >> y[i]; 
  }
  for (int l = 1; l <= q; l += B) {
    reset(); 
    vector<int> ask, upd;
    for (int i = l; i < min(q + 1, l + B); ++i) {
      if (t[i] == 1) {
        changed[x[i]] = 1; 
        upd.push_back(i); 
      } else {
        ask.push_back(i);
      }
    }
    for (int i = l; i < min(q + 1, l + B); ++i) {
      if (t[i] == 1) {
        d[x[i]] = y[i]; 
      } else {
        to_join[i - l].clear(); 
        for (int j : upd) {
          if (d[x[j]] >= y[i]) {
            to_join[i - l].push_back(x[j]); 
          }
        }
      }
    }
    vector<int> unchanged; 
    for (int i = 1; i <= m; ++i) {
      if (!changed[i]) {
        unchanged.push_back(i); 
      }
    }
    sort(ask.begin(), ask.end(), [&](int i, int j) {
      return y[i] > y[j]; 
    }); 
    sort(unchanged.begin(), unchanged.end(), [&](int i, int j) {
      return d[i] > d[j]; 
    }); 
    int ptr = 0; 
    for (int i : ask) {
      while (ptr < (int) unchanged.size() && d[unchanged[ptr]] >= y[i]) {
        unite(u[unchanged[ptr]], v[unchanged[ptr]]); 
        ptr++; 
      }
      int time = (int) stk.size();
      for (int j : to_join[i - l]) {
        unite(u[j], v[j]); 
      }
      ans[i] = sz[get(x[i])]; 
      rollback(time); 
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (t[i] == 2) {
      cout << ans[i] << ' '; 
    }
  }
  return 0;
}

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