#include "werewolf.h"
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define SIZE(c) int((c).size())
#define ALL(c) begin(c), end(c)
#define DBG(x) cerr << #x << " = " << (x) << endl
template <typename T>
ostream & operator<<(ostream &os, const vector<T> &v)
{
os << "[";
forn(i,SIZE(v))
{
if (i > 0)
os << ",";
os << v[i];
}
os << "]";
return os;
}
const int MAXN = 3500;
// minMax[0] es la normal
// minMax[1] es la opuesta (o sea que da el maxmin)
int minMax[2][MAXN][MAXN];
vector<int> neighbors[MAXN];
struct Item
{
int node;
int dist;
bool operator <(const Item &o) const
{
return dist > o.dist;
}
};
const int INF = 1000000000;
void dijkstra(int N, int start, int inverted)
{
int *dist = minMax[inverted][start];
// Siempre calcula el minMax
// Si esta inverted, usa "-nodeId"
forn(i,N)
dist[i] = INF;
priority_queue<Item> pq;
#define COST(x) (inverted ? (-x) : x)
#define PUT(node, d) do {dist[node] = d; pq.push({node, d});} while (false)
PUT(start, COST(start));
while (!pq.empty())
{
Item item = pq.top();
pq.pop();
if (dist[item.node] != item.dist)
continue;
for (int y : neighbors[item.node])
{
int newDist = max(item.dist, COST(y));
if (newDist < dist[y])
PUT(y, newDist);
}
}
if (inverted)
forn(i,N)
dist[i] = -dist[i];
}
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) {
const int M = SIZE(X);
forn(i, M)
{
#define ADD_NEIGHBOR(a,b) do {neighbors[a].push_back(b); } while (false)
ADD_NEIGHBOR(X[i],Y[i]);
ADD_NEIGHBOR(Y[i],X[i]);
}
forn(inverted, 2)
forn(start, N)
dijkstra(N, start, inverted);
const int Q = SIZE(S);
vector<int> ret(Q, 0);
forn(i,Q)
forn(mid, N)
if (minMax[1][S[i]][mid] >= L[i] &&
minMax[0][mid][E[i]] <= R[i])
{
ret[i] = 1;
break;
}
return ret;
}
