제출 #400958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400958		Hegdahl	Inside information (BOI21_servers)	C++17	100 / 100	2713 ms	280196 KiB

servers

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ar array

using namespace __gnu_pbds;
using namespace std;

using iset = tree<ar<int, 2>, null_type, less<ar<int, 2>>, rb_tree_tag, tree_order_statistics_node_update>;

const int mxN = 120'000;
const int INF = 1e9;

vector<ar<int, 2>> g[mxN];

int cut[mxN], sz[mxN];

int dfs1(int cur, int prv) {
  sz[cur] = 1;
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    sz[cur] += dfs1(nxt, cur);
  }
  return sz[cur];
}

vector<int> kids[mxN];
int find_centroid(int cur, int prv, int total) {
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (2*sz[nxt] > total) return find_centroid(nxt, cur, total);
  }

  // this is centroid

  cut[cur] = 1;
  if (prv != -1 && !cut[prv])
    dfs1(prv, -1);

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    kids[cur].push_back(find_centroid(nxt, -1, sz[nxt]));
  }

  return cur;
}

int clvl[mxN];
vector<int> cent_anc[mxN];

iset branches_start[mxN];

void set_anc(int anc, int cur, int prv) {
  cent_anc[cur].push_back(anc);

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    set_anc(anc, nxt, cur);
  }
}

gp_hash_table<int, int> out_ws[mxN], in_ws[mxN], path_end[mxN];

void init_reach_out(int root, int bw, int cur, int prv, int w) {
  out_ws[root][cur] = bw;
  path_end[root][cur] = w;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (t < w) continue;
    init_reach_out(root, bw, nxt, cur, t);
  }
}

void init_reach_in(int root, int bw, int cur, int prv, int w) {
  in_ws[root][cur] = bw;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (t > w) continue;
    init_reach_in(root, bw, nxt, cur, t);
  }
}

void init_centroid(int cur, int d) {
  clvl[cur] = d;
  for (int nxt : kids[cur])
    init_centroid(nxt, d+1);

  cent_anc[cur].push_back(cur);
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    set_anc(cur, nxt, -1);
  }

  cut[cur] = 0;

  out_ws[cur][cur] = INF;
  in_ws[cur][cur] = -INF;
  path_end[cur][cur] = -INF;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    init_reach_out(cur, t, nxt, cur, t);
    init_reach_in(cur, t, nxt, cur, t);
  }

}

bool qry(int i, int j, int t) {
  int ci = 0;
  int cj = 0;

  while (cent_anc[i][ci] != cent_anc[j][cj]) {
    if (clvl[cent_anc[i][ci]] > clvl[cent_anc[j][cj]]) ++ci;
    else if (clvl[cent_anc[j][cj]] > clvl[cent_anc[i][ci]]) ++cj;
    else ++ci, ++cj;
  }

  int lca = cent_anc[i][ci];

  auto in_it = in_ws[lca].find(j);
  auto out_it = out_ws[lca].find(i);
  if (in_it == in_ws[lca].end()) return false;
  if (out_it == out_ws[lca].end()) return false;

  if (in_it->second > t) return false;
  if (in_it->second > out_it->second) return false;
  if (path_end[lca][i] > t) return false;

  return true;
}

int count_reachable(int i, int hi) {
  int ans = 0;

  for (int root : cent_anc[i]) {
    auto reach_it = in_ws[root].find(i);
    if (reach_it == in_ws[root].end()) continue;
    int lo = reach_it->second;
    if (lo > hi) continue;
    
    ++ans;

    int here = (int)branches_start[root].size();
    if (here) {
      if (lo >= 0) here -= (int)branches_start[root].order_of_key({lo, INF});
      if (here < 0) here = 0;
    }
    ans += here;
  }

  return ans;
}

int brute_reachable(int i, int t, int n) {
  int ans = 0;
  for (int j = 0; j < n; ++j)
    ans += qry(j, i, t);
  return ans;
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);

  int n, q; cin >> n >> q;

  vector<ar<int, 3>> qs;
  vector<ar<int, 2>> cs;

  for (int t = 0; t < n+q-1; ++t) {
    char c; cin >> c;
    if (c == 'S') {
      int i, j; cin >> i >> j; --i, --j;
      g[i].push_back({j, t});
      g[j].push_back({i, t});
    } else if (c == 'Q') {
      int i, j; cin >> i >> j; --i, --j;
      qs.push_back({t, i, j});
    } else if (c == 'C') {
      int i; cin >> i; --i;
      cs.push_back({t, i});
    } else assert(0);
  }

  dfs1(0, -1);
  int root = find_centroid(0, -1, sz[0]);
  for (int i = 0; i < n; ++i)
    assert(cut[i]);

  init_centroid(root, 0);
  for (int i = 0; i < n; ++i)
    assert(!cut[i]);

  vector<pair<int, string>> ans; ans.reserve(q);

  for (auto [t, i, j] : qs)
    ans.push_back({t, qry(i, j, t)?"yes":"no"});

  vector<ar<int, 4>> upd_q;

  for (int i = 0; i < n; ++i) {
    for (int rt : cent_anc[i]) {
      if (i == rt) continue;
      auto out_it = out_ws[rt].find(i);
      if (out_it == out_ws[rt].end()) continue;
      int w_start = out_it->second;
      int w_end = path_end[rt][i];
      upd_q.push_back({w_end, w_start, rt, i});
    }
  }

  int upd_i = 0;
  sort(upd_q.begin(), upd_q.end());

  for (auto [t, i] : cs) {
    while (upd_i < (int)upd_q.size() && upd_q[upd_i][0] <= t) {
      auto [ut, w, rt, nd] = upd_q[upd_i++];
      branches_start[rt].insert({w, nd});
    }

    ans.push_back({t, to_string(count_reachable(i, t))});
  }

  sort(ans.begin(), ans.end());

  for (auto &[t, s] : ans)
    cout << s << '\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