Submission #1277584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277584		LucaLucaM	Jail (JOI22_jail)	C++20	0 / 100	10 ms	576 KiB

jail

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

#define debug(x) #x << " = " << x << '\n'

using ll = long long;
#define YES std::cout << "Yes\n"
#define NO std::cout << "No\n"

void solve() {
  int n;
  std::cin >> n;

  std::vector<std::vector<int>> g(n);

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  std::vector<int> parent(n, -1);
  std::vector<int> depth(n, 0);

  auto dfs = [&](auto &&self, int u) -> void {
    if (parent[u] != -1) {
      g[u].erase(std::find(g[u].begin(), g[u].end(), parent[u]));
    }
    for (int v : g[u]) {
      parent[v] = u;
      depth[v] = depth[u] + 1;
      self(self, v);
    }
  };

  depth[0] = 0;
  dfs(dfs, 0);

  auto lca = [&](int u, int v) {
    if (depth[u] < depth[v]) {
      std::swap(u, v);
    }
    while (depth[u] > depth[v]) {
      u = parent[u];
    }
    while (u != v) {
      u = parent[u];
      v = parent[v];
    }
    return u;
  };

  std::vector<bool> up(n, false);
  std::vector<bool> down(n, false);

  int m;
  std::cin >> m;
  while (m--) {
    int S, T;
    std::cin >> S >> T;
    S--, T--;
    int L = lca(S, T);
    while (S != L) {
      up[S] = true;
      S = parent[S];
    }
    while (T != L) {
      down[T] = true;
      T = parent[T];
    }
  }

  for (int i = 1; i < n; i++) {
    if (up[i] && down[i]) {
      NO;
      return;
    }
  }
  YES;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int t;
  std::cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    std::cerr << "Case #" << tc << ":\n";
    solve();
    std::cout << '\n';
  }

  return 0;
}

• 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