#include "werewolf.h"
#include <queue>
#include <iostream>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
VVI G;
struct State {
int form; // 0=human 1=werewolf
int city;
};
const int INF = 1000000000;
bool solve(int N, int src, int dst, int left, int right) {
VVI GG[2];
GG[0] = G; // human
GG[1] = G; // werewolf
queue<State> q;
q.push({0, src});
VVI D(2, VI(N, INF));
D[0][src] = 0;
while (!q.empty()) {
State cur = q.front(); q.pop();
if (cur.city == dst && cur.form == 1) {
return true;
}
// avanzar a la siguiente ciudad
for (int v : GG[cur.form][cur.city]) {
if (cur.form == 0) {
// soy humano
if (v < left) continue;
}
else {
// soy werewolf
if (v > right) continue;
}
State nxt = {cur.form, v};
if (D[nxt.form][nxt.city] > D[cur.form][cur.city] + 1) { // si no esta visitado en el BFS
D[nxt.form][nxt.city] = D[cur.form][cur.city] + 1;
q.push(nxt);
}
}
// transformacion en la ciudad actual: human => werewolf
if (cur.form == 0) {
if (left <= cur.city && cur.city <= right) {
State nxt = {1, cur.city};
if (D[nxt.form][nxt.city] > D[cur.form][cur.city] + 1) { // si no esta visitado en el BFS
D[nxt.form][nxt.city] = D[cur.form][cur.city] + 1;
q.push(nxt);
}
}
}
}
return false;
}
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) {
G = VVI(N);
int M = X.size();
for (int j = 0; j < M; ++j) {
int u = X[j], v = Y[j];
G[u].push_back(v);
G[v].push_back(u);
}
int Q = S.size();
vector<int> res(Q);
for (int i = 0; i < Q; ++i) {
int src = S[i], dst = E[i];
int left = L[i], right = R[i];
res[i] = solve(N, src, dst, left, right);
}
return res;
}
