Submission #867090

#	Time	Username	Problem	Language	Result	Execution time	Memory
867090		nima_aryan	Jail (JOI22_jail)	C++17	72 / 100	4959 ms	1048576 KiB

jail

/**
 *    author:  NimaAryan
 *    created: 2023-10-12 11:20:40
**/
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <class Fun>
class y_combinator_result {
  Fun fun_;
 public:
  template <class T>
  explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

  template <class ...Args>
  decltype(auto) operator()(Args&& ...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

void solve() {
  int N;
  cin >> N;
  vector<vector<int>> t(N);
  for (int i = 0; i < N - 1; ++i) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    t[A].push_back(B);
    t[B].push_back(A);
  }
  int M;
  cin >> M;
  vector<int> S(M), T(M);
  vector<int> whoS(N, -1), whoT(N, -1);
  vector<vector<pair<int, int>>> qs(N);
  for (int i = 0; i < M; ++i) {
    cin >> S[i] >> T[i];
    --S[i], --T[i];
    whoS[S[i]] = whoT[T[i]] = i;
    qs[S[i]].emplace_back(T[i], i);
    qs[T[i]].emplace_back(S[i], i);
  }
  vector<int> LCA(M);
  vector<bool> vis(N);
  vector<int> repr(N), par(N);
  auto find = y_combinator([&](auto self, int v) -> int {
    return repr[v] == v ? v : repr[v] = self(repr[v]);
  });
  auto dfs = y_combinator([&](auto self, int v) -> void {
    vis[v] = true;
    repr[v] = v;
    for (int u : t[v]) {
      if (!vis[u]) {
        par[u] = v;
        self(u);
        repr[find(u)] = v;
      }
    }
    for (auto [u, i] : qs[v]) {
      if (vis[u]) {
        LCA[i] = find(u);
      }
    }
  });
  dfs(0);
  vector<vector<int>> h(M);
  for (int i = 0; i < M; ++i) {
    auto [s, t] = pair(S[i], T[i]);
    int lca = LCA[i];
    vector<int> path{lca};
    while (s != lca) {
      path.push_back(s);
      s = par[s];
    }
    while (t != lca) {
      path.push_back(t);
      t = par[t];
    }
    for (int x : path) {
      if (whoS[x] != -1 && whoS[x] != i) {
        h[i].push_back(whoS[x]);
      }
      if (whoT[x] != -1 && whoT[x] != i) {
        h[whoT[x]].push_back(i);
      }
    }
  }
  vector<int> seen(M);
  bool fail = false;
  auto check = y_combinator([&](auto self, int v) -> void {
    seen[v] = 1;
    for (int u : h[v]) {
      if (!seen[u]) {
        self(u);
      } else if (seen[u] == 1) {
        fail = true;
      }
    }
    seen[v] = 2;
  });
  for (int i = 0; i < M; ++i) {
    if (!seen[i]) {
      check(i);
    }
  }
  cout << (fail ? "No" : "Yes") << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int Q;
  cin >> Q;
  while (Q--) {
    solve();
  }
  return 0;
}

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