Submission #1179303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179303		tch1cherin	Jail (JOI22_jail)	C++20	0 / 100	16 ms	328 KiB

jail

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

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; i++) {
      int A, B;
      cin >> A >> B;
      --A, --B;
      graph[A].push_back(B);
      graph[B].push_back(A);
    }
    int M;
    cin >> M;
    vector<int> S(M), T(M);
    for (int i = 0; i < M; i++) {
      cin >> S[i] >> T[i];
      --S[i], --T[i];
    }
    vector<int> parent(N), sizes(N);
    auto DFS = [&](auto&& self, int u, int par) -> void {
      if (par != -1) {
        graph[u].erase(find(graph[u].begin(), graph[u].end(), par));
      }
      parent[u] = par;
      sizes[u] = 1;
      for (int &v : graph[u]) {
        self(self, v, u);
        sizes[u] += sizes[v];
        if (sizes[v] > sizes[graph[u][0]]) {
          swap(v, graph[u][0]);
        }
      }
    };
    vector<int> tin(N), tout(N), head(N);
    int tin_cur = 0;
    auto BuildHLD = [&](auto&& self, int u) -> void {
      tin[u] = tin_cur++;
      for (int v : graph[u]) {
        head[v] = (v == graph[u][0] ? head[u] : v); 
        self(self, v);
      }
      tout[u] = tin_cur;
    };
    DFS(DFS, 0, -1);
    BuildHLD(BuildHLD, 0);
    vector<vector<int>> seg(4 * N + M);
    for (int i = N - 1; i > 0; i--) {
      seg[i * 2].push_back(i);
      seg[i * 2 + 1].push_back(i);
      seg[2 * N + i].push_back(2 * N + i * 2);
      seg[2 * N + i].push_back(2 * N + i * 2 + 1);
    }
    for (int i = 0; i < M; i++) {
      seg[4 * N + i].push_back(N + S[i]);
      seg[3 * N + T[i]].push_back(4 * N + i);
    }
    auto AddEdge = [&](int u, int l, int r) {
      for (int side = 0; side < 2; side++) {
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
          auto Add = [&](int v) {
            if (side == 0) {
              seg[2 * N * side + v].push_back(4 * N + u);
            } else {
              seg[4 * N + u].push_back(2 * N * side + v); 
            }
          };
          if (l & 1) {
            Add(l++);
          }
          if (r & 1) {
            Add(--r);
          }
        }
      }
    };
    auto IsAncestor = [&](int u, int v) {
      return tin[u] <= tin[v] && tout[v] <= tout[u];
    };
    for (int i = 0; i < M; i++) {
      int s = S[i], t = T[i], delta = 0;
      while (!IsAncestor(head[s], t)) {
        AddEdge(i, tin[head[s]], tin[s] + delta);
        s = parent[head[s]];
        delta = 1;
      }
      while (!IsAncestor(head[t], s)) {
        AddEdge(i, tin[head[t]], tin[t] + 1); 
        t = parent[head[t]];
      }
      if (IsAncestor(s, t)) {
        AddEdge(i, tin[s] + !delta, tin[t] + 1);
      } else {
        AddEdge(i, tin[t], tin[s] + delta);
      }
    }
    vector<int> color(4 * N + M);
    auto FindCycle = [&](auto&& self, int u) -> bool {
      color[u] = 2;
      for (int v : seg[u]) {
        if (color[v] == 2) {
          return true;
        }
        if (!color[v] && self(self, v)) {
          return true;
        }
      }
      color[u] = 1;
      return false;
    };
    bool good = true;
    for (int i = 0; i < 4 * N + M; i++) {
      if (!color[i] && FindCycle(FindCycle, i)) {
        good = false;
      }
    }
    cout << (good ? "Yes\n" : "No\n");
  }
}

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