#include <bits/stdc++.h> #include "werewolf.h" using namespace std; #define pb push_back #define sz(x) (int)x.size() #define all(x) (x).begin(), (x).end() typedef vector<int> vii; typedef pair<int, int> pii; const int M = 2e3+5; vector <vii> g(M),v(M); int par[M]; int cur; int in1[M],out1[M]; int in2[M],out2[M]; int x[M],y[M]; pii Lr[M],Rr[M]; int px[M],py[M]; int Arr[M]; int up1[20][M],up2[20][M]; int vis[M]; vector <vii> t(M*4); void cleardsu() { cur = 0; for (int i = 0; i < M; i++) { vis[i] = 0; par[i] = i; v[i].clear(); } } int getpar(int x) { if (x == par[x]) return x; return par[x] = getpar(par[x]); } void dfs1(int x, int p) { vis[x] = 1; in1[x] = cur++; up1[0][x] = p; for (int i = 1; i <= 18; i++) { if (up1[i-1][x] != -1) up1[i][x] = up1[i-1][up1[i-1][x]]; else up1[i][x] = -1; } for (auto to:v[x]) { if (to == p) continue; dfs1(to,x); } out1[x] = cur; } void dfs2(int x, int p) { vis[x] =1; in2[x] = cur++; up2[0][x] = p; for (int i = 1; i <= 18; i++) { if (up2[i-1][x] != -1) up2[i][x] = up2[i-1][up2[i-1][x]]; else up2[i][x] = -1; } for (auto to:v[x]) { if (to == p) continue; dfs2(to,x); } out2[x] = cur; } vii merge(vii a, vii b) { vii res; int pos1 = 0; int pos2 = 0; while (pos1 < sz(a) && pos2 < sz(b)) { if (a[pos1] < b[pos2]) { res.pb(a[pos1]); pos1++; } else { res.pb(b[pos2]); pos2++; } } while (pos2 < sz(b)) { res.pb(b[pos2]); pos2++; } while (pos1 < sz(a)) { res.pb(a[pos1]); pos1++; } return res; } void build(int node, int l, int r) { if (l == r) { t[node].pb(Arr[l]); return; } int mid = (l+r)/2; build (node*2,l,mid); build(node*2+1,mid+1,r); t[node] = merge(t[node*2],t[node*2+1]); } bool getans(int node, int l, int r, int lx, int rx, int ly, int ry) { if (r < lx || l > rx) return 0; if (l >= lx && r <= rx) { auto it = lower_bound(all(t[node]),ly); return (it != t[node].end() && *it <= ry); } int mid = (l+r)/2; return (getans(node*2,l,mid,lx,rx,ly,ry) || getans(node*2+1,mid+1,r,lx,rx,ly,ry)); } 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(); vector<int> A(Q); for (int i = 0; i < Q; ++i) { A[i] = 0; } for (int i = 0; i < sz(X); i++) { g[X[i]].pb(Y[i]); g[Y[i]].pb(X[i]); } cleardsu(); for (int i = N-1; i >= 0; i--) { for (auto to: g[i]) { if (to >= i) { int a = getpar(to); if (a != i) { par[a] = i; v[i].pb(a); } } } } for (int i = 0; i < N; i++) { if (!vis[getpar(i)]) { dfs1(getpar(i),-1); } } cleardsu(); for (int i = 0; i < N; i++) { for (auto to:g[i]) { if (to <= i) { int a = getpar(to); if (a != i) { par[a] = i; v[i].pb(to); } } } } for (int i = 0; i < N; i++) { if (!vis[getpar(i)]) { dfs2(getpar(i),-1); } } cleardsu(); for (int i = 0; i < N; i++) { Arr[in1[i]] = in2[i]; } build (1,0,N-1); int q = 0; while (q < Q) { int st = S[q]; int ed = E[q]; for (int i = 18; i >= 0; i--) { if (up1[i][st] != -1 && up1[i][st] >= L[q]) st = up1[i][st]; } for (int i = 18; i >= 0; i--) { if (up2[i][ed] != -1 && up2[i][ed] <= R[q]) ed = up2[i][ed]; } int lx = in1[st]; int rx = out1[st]-1; int ly = in2[ed]; int ry = out2[ed]-1; if (st < L[q] || ed > R[q]) { A[q] = 0; q++; continue; } A[q] = getans(1,0,N-1,lx,rx,ly,ry); q++; } return A; }