#include "werewolf.h" #include <queue> std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { int Q = S.size(); std::vector<int> A(Q); for (int i = 0; i < Q; ++i) { A[i] = 0; } int M = X.size(); std::vector<std::vector<int>> adj(N); for (int i = 0; i < M; ++i) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } for (int qi = 0; qi < Q; ++qi) { int s = S[qi], e = E[qi]; int lo = L[qi], hi = R[qi]; std::vector<bool> visS(N, false); std::queue<int> q1; visS[s] = true, q1.push(s); while (q1.size()) { int u = q1.front(); q1.pop(); for (int v : adj[u]) if (!visS[v] && v >= lo) visS[v] = true, q1.push(v); } std::vector<bool> visE(N, false); std::queue<int> q2; visE[e] = true, q2.push(e); while (q2.size()) { int u = q2.front(); q2.pop(); for (int v : adj[u]) if (!visE[v] && v <= hi) visE[v] = true, q2.push(v); } bool ok = false; for (int t = lo; t <= hi; ++t) if (visS[t] && visE[t]) { ok = true; break; } A[qi] = ok; } return A; }