Submission #701018

#	Time	Username	Problem	Language	Result	Execution time	Memory
701018		BingDong	Jail (JOI22_jail)	C++17	100 / 100	441 ms	72192 KiB

jail

#include <iostream>
#include <vector>
using namespace std;

int read() {
  int s = 0, w = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-')
      w = -1;
    c = getchar();
  }
  while (isdigit(c))
    s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
  return s * w;
}

const int N = 1.2e5, Q = 1.2e5, N_ = (1 << 17) * 4 + Q;

vector<int> g[N];
int p[N], c[N], o[N], z[N], tt;

int dfs1(int i) {
  int s = 1, x = 0;
  c[i] = -1;
  for (int j : g[i])
    if (p[i] != j) {
      p[j] = i;
      int y = dfs1(j);
      if (y > x)
        x = y, c[i] = j;
      s += y;
    }
  return s;
}

void dfs2(int i, int z_) {
  z[i] = z_;
  o[i] = tt++;
  if (c[i] != -1)
    dfs2(c[i], z_);
  for (int j : g[i])
    if (p[i] != j && c[i] != j)
      dfs2(j, j);
}

int n_, d[N_];
vector<int> g_[N_];

void add_edge(int i, int j) {
  g_[i].push_back(j), d[j]++;
}

void dfs(int i) {
  if (d[i] == 0) {
    d[i] = -1;
    for (int j : g_[i]) {
      d[j]--;
      dfs(j);
    }
  }
}

void add_range(int l, int r, int s, int t, int h) {
  int x, y;
  x = l + (o[t] == l), y = r - (o[t] == r);
  for (x += n_, y += n_; x <= y; x >>= 1, y >>= 1) {
    if ((x & 1) == 1)
      add_edge(n_ * 4 + h, x), x++;
    if ((y & 1) == 0)
      add_edge(n_ * 4 + h, y), y--;
  }
  x = l + (o[s] == l), y = r - (o[s] == r);
  for (x += n_, y += n_; x <= y; x >>= 1, y >>= 1) {
    if ((x & 1) == 1)
      add_edge(n_ * 2 + x, n_ * 4 + h), x++;
    if ((y & 1) == 0)
      add_edge(n_ * 2 + y, n_ * 4 + h), y--;
  }
}

int main() {
  int t = read();
  while (t--) {
    int n = read();
    for (int h = 0; h < n - 1; h++) {
      int i = read() - 1, j = read() - 1;
      g[i].push_back(j), g[j].push_back(i);
    }
    p[0] = -1;
    dfs1(0);
    tt = 0;
    dfs2(0, 0);
    n_ = 1;
    while (n_ < n)
      n_ <<= 1;
    for (int i = 1; i < n_; i++) {
      add_edge(i, i << 1 | 0);
      add_edge(i, i << 1 | 1);
      add_edge(n_ * 2 + (i << 1 | 0), n_ * 2 + i);
      add_edge(n_ * 2 + (i << 1 | 1), n_ * 2 + i);
    }
    int q = read();
    for (int h = 0; h < q; h++) {
      int s = read() - 1, t = read() - 1, i = s, j = t;
      while (z[i] != z[j])
        if (o[z[i]] > o[z[j]])
          add_range(o[z[i]], o[i], s, t, h), i = p[z[i]];
        else
          add_range(o[z[j]], o[j], s, t, h), j = p[z[j]];
      add_range(min(o[i], o[j]), max(o[i], o[j]), s, t, h);
      add_edge(n_ + o[t], n_ * 4 + h);
      add_edge(n_ * 4 + h, n_ * 3 + o[s]);
    }
    for (int i = 1; i < n_ * 4 + q; i++)
      dfs(i);
    bool yes = 1;
    for (int i = 1; i < n_ * 4 + q; i++)
      yes &= d[i] == -1;
    printf(yes ? "Yes\n" : "No\n");
    for (int i = 0; i < n; i++)
      g[i].clear();
    for (int i = 1; i < n_ * 4 + q; i++) {
      g_[i].clear();
      d[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