#include "werewolf.h" #include <bits/stdc++.h> using namespace std; struct KRT { int N, LOG; vector<vector<int>> child; vector<int> parent; // parent in KRT, 0 = super-root vector<int> tin, tout; // Euler tin/tout for vertices 1..N vector<int> euler; // euler[t] = vertex at time t, t in 1..N vector<vector<int>> up; // binary lifting KRT(int n = 0) { init(n); } void init(int n) { N = n; child.assign(N + 1, {}); parent.assign(N + 1, 0); tin.assign(N + 1, 0); tout.assign(N + 1, 0); euler.assign(N + 1, 0); LOG = 1; while ((1 << LOG) <= N) ++LOG; up.assign(LOG, vector<int>(N + 1, 0)); } void build_lift() { for (int i = 1; i <= N; ++i) up[0][i] = parent[i]; for (int k = 1; k < LOG; ++k) { for (int i = 1; i <= N; ++i) { up[k][i] = up[k - 1][ up[k - 1][i] ]; } } } // iterative DFS from super-root 0; assigns tin/tout for all vertices 1..N void build_euler() { int timer = 0; vector<int> it(N + 1, 0); vector<int> st; st.push_back(0); while (!st.empty()) { int u = st.back(); if (u != 0 && it[u] == 0) { tin[u] = ++timer; euler[timer] = u; } if (it[u] < (int)child[u].size()) { int v = child[u][it[u]++]; st.push_back(v); } else { if (u != 0) tout[u] = timer; st.pop_back(); } } } }; static KRT build_left_krt(int N, const vector<vector<int>>& adj) { KRT krt(N); vector<int> dsu(N + 1), active(N + 1, 0), stamp(N + 1, 0); auto find_set = [&](auto&& self, int v) -> int { if (dsu[v] == v) return v; return dsu[v] = self(self, dsu[v]); }; for (int i = 1; i <= N; ++i) dsu[i] = i; for (int i = N; i >= 1; --i) { active[i] = 1; dsu[i] = i; vector<int> reps; for (int j : adj[i]) if (active[j]) { int r = find_set(find_set, j); if (r == i) continue; if (stamp[r] != i) { stamp[r] = i; reps.push_back(r); } } for (int r : reps) { krt.child[i].push_back(r); krt.parent[r] = i; } for (int r : reps) dsu[r] = i; } // connect component roots to super-root 0 for (int v = 1; v <= N; ++v) { int r = find_set(find_set, v); if (r == v && krt.parent[v] == 0) { krt.child[0].push_back(v); krt.parent[v] = 0; } } krt.build_euler(); krt.build_lift(); return krt; } static KRT build_right_krt(int N, const vector<vector<int>>& adj) { KRT krt(N); vector<int> dsu(N + 1), active(N + 1, 0), stamp(N + 1, 0); auto find_set = [&](auto&& self, int v) -> int { if (dsu[v] == v) return v; return dsu[v] = self(self, dsu[v]); }; for (int i = 1; i <= N; ++i) dsu[i] = i; for (int i = 1; i <= N; ++i) { active[i] = 1; dsu[i] = i; vector<int> reps; for (int j : adj[i]) if (active[j]) { int r = find_set(find_set, j); if (r == i) continue; if (stamp[r] != i) { stamp[r] = i; reps.push_back(r); } } for (int r : reps) { krt.child[i].push_back(r); krt.parent[r] = i; } for (int r : reps) dsu[r] = i; } // connect component roots to super-root 0 for (int v = 1; v <= N; ++v) { int r = find_set(find_set, v); if (r == v && krt.parent[v] == 0) { krt.child[0].push_back(v); krt.parent[v] = 0; } } krt.build_euler(); krt.build_lift(); return krt; } static int lift_left(const KRT& krt, int u, int L) { for (int k = krt.LOG - 1; k >= 0; --k) { int a = krt.up[k][u]; if (a != 0 && a >= L) u = a; } return u; } static int lift_right(const KRT& krt, int u, int R) { for (int k = krt.LOG - 1; k >= 0; --k) { int a = krt.up[k][u]; if (a != 0 && a <= R) u = a; } return u; } 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 M = (int)X.size(); int Q = (int)S.size(); // IOI werewolf is 0-based (0..N-1). Shift to 1-based internally if it looks 0-based. int mx = -1; auto upd_mx = [&](const vector<int>& a){ for (int v: a) mx = max(mx, v); }; upd_mx(X); upd_mx(Y); upd_mx(S); upd_mx(E); upd_mx(L); upd_mx(R); if (mx <= N - 1) { for (int &v : X) ++v; for (int &v : Y) ++v; for (int &v : S) ++v; for (int &v : E) ++v; for (int &v : L) ++v; for (int &v : R) ++v; } vector<vector<int>> adj(N + 1); for (int i = 0; i < M; ++i) { int a = X[i], b = Y[i]; adj[a].push_back(b); adj[b].push_back(a); } KRT left = build_left_krt(N, adj); KRT right = build_right_krt(N, adj); // BIT over left Euler positions vector<int> bit(N + 1, 0); auto bit_add = [&](int pos) { for (; pos <= N; pos += pos & -pos) bit[pos] += 1; }; auto bit_sum = [&](int pos) { int r = 0; for (; pos > 0; pos -= pos & -pos) r += bit[pos]; return r; }; auto bit_query = [&](int l, int r) { if (l > r) return 0; return bit_sum(r) - bit_sum(l - 1); }; vector<vector<int>> evL(N + 1), evR(N + 1); vector<int> l1(Q, 0), r1(Q, -1), l2(Q, 0), r2(Q, -1); vector<int> ans(Q, 0); for (int i = 0; i < Q; ++i) { int s = S[i], e = E[i], l = L[i], r = R[i]; // necessary condition (phases): start must be >=L, end must be <=R if (s < l || e > r) { ans[i] = 0; continue; } int u = lift_left(left, s, l); // component(S) in induced >=L int v = lift_right(right, e, r); // component(E) in induced <=R l1[i] = left.tin[u]; r1[i] = left.tout[u]; l2[i] = right.tin[v]; r2[i] = right.tout[v]; evR[r2[i]].push_back(i); evL[l2[i] - 1].push_back(i); // l2>=1 always (all nodes visited) } // sweep t = 0..N: maintain prefix of right Euler, mark their positions in left Euler for (int t = 0; t <= N; ++t) { if (t >= 1) { int x = right.euler[t]; bit_add(left.tin[x]); } for (int id : evL[t]) ans[id] -= bit_query(l1[id], r1[id]); for (int id : evR[t]) ans[id] += bit_query(l1[id], r1[id]); } for (int i = 0; i < Q; ++i) ans[i] = (ans[i] > 0 ? 1 : 0); return ans; }