Submission #894233

#	Time	Username	Problem	Language	Result	Execution time	Memory
894233		box	Jail (JOI22_jail)	C++17	100 / 100	1190 ms	307884 KiB

jail

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
const int N = 1.2e5, H = 17, N_ = N + 2 * N * H;
 
vector<int> g[N], q[N_];
int p[H][N], d[N], w[N_];
 
inline int z(int i, int h, int t) { return (i * H + h) * 2 + t; }
 
void dfs(int i) {
  for (int h = 0; h < H - 1; h++) {
    p[h + 1][i] = p[h][p[h][i]];
    q[z(i, h, 0)].push_back(z(i, h + 1, 0));
    q[z(p[h][i], h, 0)].push_back(z(i, h + 1, 0));
    q[z(i, h + 1, 1)].push_back(z(i, h, 1));
    q[z(i, h + 1, 1)].push_back(z(p[h][i], h, 1));
  }
  for (int j : g[i])
    if (p[0][i] != j) {
      p[0][j] = i;
      d[j] = d[i] + 1;
      dfs(j);
    }
}
 
int lca(int i, int j) {
  if (d[i] < d[j]) swap(i, j);
  int k = d[i] - d[j];
  for (int h = 0; h < H; h++)
    if (k >> h & 1) i = p[h][i];
  if (i == j) return i;
  for (int h = H - 1; h >= 0; h--)
    if (p[h][i] != p[h][j]) i = p[h][i], j = p[h][j];
  return p[0][i];
}
 
template <class F>
void up(int i, int k, const F& f) {
  if (k < 0) return;
  for (int h = 0; h < H; h++)
    if (k >> h & 1) f(i, h), i = p[h][i];
  f(i, 0);
}
 
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int h = 0; h < n - 1; h++) {
      int i, j;
      cin >> i >> j, i--, j--;
      g[i].push_back(j), g[j].push_back(i);
    }
    dfs(0);
    int m;
    cin >> m;
    for (int h = 0; h < m; h++) {
      int i, j;
      cin >> i >> j, i--, j--;
      q[n * H * 2 + h].push_back(z(i, 0, 0));
      q[z(j, 0, 1)].push_back(n * H * 2 + h);
      int f = lca(i, j);
      if (i != f) {
        up(p[0][i], d[i] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
        up(j, d[j] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
      } else
        up(j, d[j] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
      if (j != f) {
        up(p[0][j], d[j] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
        up(i, d[i] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
      } else
        up(i, d[i] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
    }
    for (int i = 0; i < n * H * 2 + m; i++)
      for (int j : q[i]) w[j]++;
    vector<int> o;
    for (int i = 0; i < n * H * 2 + m; i++)
      if (!w[i]) o.push_back(i);
    for (int u = 0; u < (int)o.size(); u++) {
      int i = o[u];
      for (int j : q[i])
        if (--w[j] == 0) o.push_back(j);
    }
    cout << ((int)o.size() == n * H * 2 + m ? "Yes\n" : "No\n");
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < n * H * 2 + m; i++) q[i].clear(), w[i] = 0;
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23