#include "werewolf.h"
using namespace std;
/*
Lemma:
This problem is hard. I will try dfs for subtask 1 and 2, which is 15/100
[working]
*/
vector<int> A;
vector<int> RH, RW;
vector<vector<int>> adj;
void dfs(int node, bool mode, int lim, int i){
if(!mode){
// human form (0)
for(auto v:adj[node]){
if(RH[v] == i)continue; // if we've already been here..
if(v >= lim){
RH[v] = i;
dfs(v, mode, lim, i);
}
}
} else{
// werewolf form (1)
if(A[i])return;
if(RH[node]==i){
A[i]=1;
return;
}
for(auto v:adj[node]){
if(RW[v] == i)continue; // if we've already been here..
if(v <= lim){
RW[v] = i;
dfs(v, mode, lim, i);
}
}
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size();
int M = X.size();
A = vector<int>(Q, 0); // answer
// --- init stuff ---
// setting up the adjacency matrix
adj = vector<vector<int>>(N);
int u,v;
for(int i=0; i<M; i++){
u = X[i];
v = Y[i];
// u,v are the nodes that are connected..
adj[u].push_back(v);
adj[v].push_back(u);
}
// --- ### ---
RH = vector<int>(N, -1);
RW = vector<int>(N, -1);
for (int i = 0; i < Q; ++i) {
// first, do dfs on the human paths
RH[S[i]] = i;
dfs(S[i], 0, L[i], i);
// at the end of this process, we have filled the vector RH, such that the cities which are reachable via human form have value `i` specifically.
A[i]=0;
// now, do dfs on the werewolf paths, and check to see if we reach any human paths. This can be checked with (? RH[node]==i)
RW[E[i]] = i;
A[i]=0;
dfs(E[i], 1, R[i], i);
// ..
}
return A;
}
