#include <bits/stdc++.h> #include "werewolf.h" using namespace std; vector<vector<int>> g, mn, mx; vector<bool> vis; void dfs(int u) { vis[u] = 1; for (auto v : g[u]) { if (!vis[v]) { dfs(v); } } } 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 m = x.size(); mn.resize(n + 1, vector<int>(n + 1)); mx.resize(n + 1, vector<int>(n + 1)); auto get_max = [&](int s, int e) { int l = 1, r = n + 1; while (l + 1 < r) { int k = (l + r) / 2; g.assign(n + 1, {}); vis.assign(n + 1, 0); for (int i = 0; i < m; i++) { if (min(x[i], y[i]) >= k) { g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } } dfs(s); if (vis[e]) { l = k; } else { r = k; } } return l; }; auto get_min = [&](int s, int e) { int l = 0, r = n; while (l + 1 < r) { int k = (l + r) / 2; g.assign(n + 1, {}); vis.assign(n + 1, 0); for (int i = 0; i < m; i++) { if (max(x[i], y[i]) <= k) { g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } } dfs(s); if (vis[e]) { r = k; } else { l = k; } } return r; }; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { mx[i][j] = get_max(i, j); mn[i][j] = get_min(i, j); } } int q = S.size(); vector<int> ans(q); for (int i = 0; i < q; i++) { int s = S[i], e = E[i], l = L[i], r = R[i]; for (int j = l; j <= r; j++) { if (mx[s][j] >= l && mn[j][e] <= r) { ans[i] = 1; break; } } } return ans; }