Submission #1179367

#TimeUsernameProblemLanguageResultExecution timeMemory
1179367tch1cherinJail (JOI22_jail)C++20
100 / 100
295 ms75592 KiB
#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 + tin[S[i]]);
      seg[3 * N + tin[T[i]]].push_back(4 * N + i);
    }
    auto AddEdge = [&](int u, int l, int r, int side) -> void {
      for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        auto Add = [&](int v) {
          if (side == 0) {
            seg[v].push_back(4 * N + u);
          } else {
            seg[4 * N + u].push_back(2 * N + 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, 0);
        s = parent[head[s]];
        delta = 1;
      }
      while (!IsAncestor(head[t], s)) {
        AddEdge(i, tin[head[t]], tin[t] + 1, 0);
        t = parent[head[t]];
      }
      if (IsAncestor(s, t)) {
        AddEdge(i, tin[s] + !delta, tin[t] + 1, 0);
      } else {
        AddEdge(i, tin[t], tin[s] + delta, 0);
      }
      s = S[i], t = T[i], delta = 0;
      while (!IsAncestor(head[s], t)) {
        AddEdge(i, tin[head[s]], tin[s] + 1, 1);
        s = parent[head[s]];
      }
      while (!IsAncestor(head[t], s)) {
        AddEdge(i, tin[head[t]], tin[t] + delta, 1);
        t = parent[head[t]];
        delta = 1;
      }
      if (IsAncestor(s, t)) {
        AddEdge(i, tin[s], tin[t] + delta, 1);
      } else {
        AddEdge(i, tin[t] + !delta, tin[s] + 1, 1);
      }
    }
    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");
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...