제출 #807552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807552		dong_liu	Inside information (BOI21_servers)	C++17	100 / 100	637 ms	96724 KiB

servers

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

const int N = 120000, L = 17;

int pp[L][N], dd[N], vv[N], up[N], dn[N];
vector<pair<int, int>> g[N];

void dfs(int i) {
  for (int l = 1; l < L; l++) pp[l][i] = pp[l - 1][pp[l - 1][i]];
  for (auto [j, h] : g[i])
    if (j != pp[0][i]) {
      vv[j] = h;
      if (i == 0)
        up[j] = dn[j] = i;
      else if (vv[j] > vv[i])
        up[j] = up[i], dn[j] = i;
      else
        up[j] = i, dn[j] = dn[i];
      dd[j] = dd[i] + 1;
      pp[0][j] = i;
      dfs(j);
    }
}
int jmp(int i, int k) {
  for (int l = 0; l < L; l++)
    if (k >> l & 1) i = pp[l][i];
  return i;
}
int lca(int i, int j) {
  if (dd[i] < dd[j]) swap(i, j);
  i = jmp(i, dd[i] - dd[j]);
  if (i == j) return i;
  for (int l = L - 1; l >= 0; l--)
    if (pp[l][i] != pp[l][j]) i = pp[l][i], j = pp[l][j];
  return pp[0][i];
}
bool has(int i, int j, int h) {
  if (i == j) return 1;
  int p = lca(i, j);
  if (p == i)
    return (dd[dn[j]] <= dd[i] && vv[jmp(j, dd[j] - dd[i] - 1)] < h);
  else if (p == j)
    return (dd[up[i]] <= dd[j] && vv[i] < h);
  else
    return (dd[up[i]] <= dd[p] && dd[dn[j]] <= dd[p] &&
            vv[jmp(i, dd[i] - dd[p] - 1)] > vv[jmp(j, dd[j] - dd[p] - 1)] &&
            vv[i] < h);
}

int cp[N], sz[N];
bool dead[N];
vector<int> cup[N], cen[N], eds;
vector<pair<int, int>> upd[N * 2];

struct FT {
  vector<int> t, inds;
  int all;

  void bld(vector<int> inds_) {
    inds = inds_;
    sort(inds.begin(), inds.end());
    t.assign(inds.size(), 0);
    all = 0;
  }
  void upd(int i) {
    i = lower_bound(inds.begin(), inds.end(), i) - inds.begin();
    while (i < (int)inds.size()) t[i]++, i |= i + 1;
    all++;
  }
  int qry(int i) {  // # > i
    i = lower_bound(inds.begin(), inds.end(), i) - inds.begin();
    int x = all;
    while (i >= 0) x -= t[i], i &= i + 1, i--;
    return x;
  }
} ft[N];

int dfs1(int p, int i) {
  sz[i] = 1;
  for (auto [j, h] : g[i])
    if (p != j && !dead[j]) sz[i] += dfs1(i, j);
  return sz[i];
}
int dfs2(int p, int i, int n) {
  for (auto [j, h] : g[i])
    if (p != j && !dead[j] && sz[j] * 2 > n) return dfs2(i, j, n);
  return i;
}
void dfs3(int c, int p, int i, int htop, int hlast, bool up, bool dn) {
  cen[i].push_back(c);
  cup[i].push_back(up ? htop : -1);
  if (dn) {
    upd[hlast].push_back({c, htop});
  }
  for (auto [j, h] : g[i])
    if (p != j && !dead[j]) {
      eds.push_back(h);
      dfs3(c, i, j, htop, h, up && h < hlast, dn && h > hlast);
    }
}
void cd(int p, int i) {
  i = dfs2(-1, i, dfs1(-1, i));
  cp[i] = p;
  dead[i] = 1;
  for (auto [j, h] : g[i])
    if (!dead[j]) {
      eds.push_back(h);
      dfs3(i, i, j, h, h, 1, 1);
    }
  ft[i].bld(eds);
  vector<int>().swap(eds);
  for (auto [j, h] : g[i])
    if (!dead[j]) cd(i, j);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<array<int, 3>> qry;
  for (int h = 0; h < n + q - 1; h++) {
    char t;
    cin >> t;
    if (t == 'S') {
      int i, j;
      cin >> i >> j, i--, j--;
      g[i].push_back({j, h}), g[j].push_back({i, h});
    } else if (t == 'Q') {
      int i, j;
      cin >> i >> j, i--, j--;
      qry.push_back({i, j, h});
    } else {
      int i;
      cin >> i, i--;
      qry.push_back({-1, i, h});
    }
  }
  pp[0][0] = 0;
  dfs(0);
  for (int i = 0; i < n; i++) cp[i] = -1;
  cd(-1, 0);
  for (int i = 0; i < n; i++) {
    reverse(cen[i].begin(), cen[i].end());
    reverse(cup[i].begin(), cup[i].end());
  }
  int ch = 0;
  for (int h_ = 0; h_ < q; h_++) {
    auto [i, j, h] = qry[h_];
    while (ch <= h) {
      for (auto [c, h] : upd[ch]) ft[c].upd(h);
      ch++;
    }
    if (i == -1) {
      i = j;
      int cnt = 1 + ft[i].all, c = cp[i], d = 0;
      while (~c) {
        if (~cup[i][d] && cup[i][d] < h) {
          int x = 1 + ft[c].qry(cup[i][d]);
          cnt += x;
        }
        c = cp[c], d++;
      }
      cout << cnt << '\n';
    } else {
      cout << (has(i, j, h) ? "yes\n" : "no\n");
    }
  }
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5