제출 #701008

#제출 시각아이디문제언어결과실행 시간메모리
701008dongliu0426Jail (JOI22_jail)C++17
26 / 100
412 ms70364 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
 
namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;
 
template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
 
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;
 
const int N = 1.25e5, M = 5 * N;
 
vector<int> g[N], g2[M];
 
char used[M];
 
bool dfs_cycle(int u) {
  if (used[u] == 1) {
    return false;
  }
  used[u] = 1;
  for (int v : g2[u]) {
    if (used[v] != 2 && !dfs_cycle(v)) {
      return false;
    }
  }
  used[u] = 2;
  return true;
}
 
int sz[N];
 
int dfs_sz(int u = 0, int p = -1) {
  int res = 1;
  for (int v : g[u]) {
    if (v != p) {
      res += dfs_sz(v, u);
    }
  }
  return sz[u] = res;
}
 
int timer, order[N], lnk[N], tout[N], parent[N];
 
void dfs_hld(int u = 0, int up = 0, int p = -1) {
  order[u] = timer;
  parent[timer] = p == -1 ? -1 : order[p];
  lnk[timer] = order[up];
  ++timer;
  sort(all(g[u]), [](int x, int y) {
    return sz[x] > sz[y];
  });
  bool is_first = true;
  for (int v : g[u]) {
    if (v != p) {
      dfs_hld(v, is_first ? up : v, u);
      is_first = false;
    }
  }
  tout[order[u]] = timer;
}
 
bool in(int x0, int y0, int x1, int y1) {
  return x0 <= x1 && y1 <= y0;
}
 
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int testcases;
  cin >> testcases;
  while (testcases--) {
    int n, m;
    cin >> n;
    for (int i = 0; i < 5 * n; ++i) {
      g2[i].clear();
    }
    for (int i = 0; i < n; ++i) {
      g[i].clear();
    }
    for (int i = 1; i < n; ++i) {
      int u, v;
      cin >> u >> v;
      g[--u].push_back(--v);
      g[v].push_back(u);
    }
    timer = 0;
    dfs_sz();
    dfs_hld();
    assert(timer == n);
 
    cin >> m;
 
 
    for (int i = 2 * n - 1; i > 0; --i) {
      g2[i / 2].push_back(i);
      g2[2 * n + i].push_back(2 * n + i / 2);
    }
 
    for (int person = 0; person < m; ++person) {
      int u = 4 * n + person;
 
      int s, t;
      cin >> s >> t;
      s = order[s - 1], t = order[t - 1];
 
      auto use_cut = [&](int l, int r) {
        int x = n + l + (l == s ? 1 : 0), y = n + r - (r == s ? 1 : 0);
        while (x <= y) {
          if (x & 1)  g2[u].push_back(x);
          if (!(y & 1)) g2[u].push_back(y);
          x = (x + 1) / 2;
          y = (y - 1) / 2;
        }
        // for (int i = l; i <= r; ++i) {
        //  if (i != s) {
        //    g2[u].push_back(n + i);
        //  }
        // }
 
        x = n + l + (l == t ? 1 : 0), y = n + r - (r == t ? 1 : 0);
        while (x <= y) {
          if (x & 1)  g2[2 * n + x].push_back(u);
          if (!(y & 1)) g2[2 * n + y].push_back(u);
          x = (x + 1) / 2;
          y = (y - 1) / 2;
        }
        // for (int i = l; i <= r; ++i) {
        //  if (i != t) {
        //    g2[3 * n + i].push_back(u);
        //  }
        // }
      };
 
      int a = s, b = t;
      while (lnk[a] != lnk[b]) {
        if (order[lnk[a]] > order[lnk[b]]) {
          use_cut(lnk[a], a);
          a = parent[lnk[a]];
        } else {
          // assert(!in(lnk[b], tout[lnk[b]], a, tout[a]));
          use_cut(lnk[b], b);
          b = parent[lnk[b]];
        }
      }
      use_cut(min(a, b), max(a, b));
      g2[n + s].push_back(u);
      g2[u].push_back(3 * n + t);
    }
    fill(used, used + 5 * n, 0);
    bool flag = true;
    for (int i = 0; i < 5 * n; ++i) {
      if (!used[i]) {
        flag &= dfs_cycle(i);
      }
    }
    cout << (flag ? "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...