#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segtree {
ll max, min;
};
vector <segtree> T;
ll k = 1;
const ll INF = 1e7;
void build(ll n, vector <ll> v){
while (k < n)k *= 2;
T.resize(2*k);
for (int i = 0; i < n; i++)T[i+k] = {v[i], v[i]};
for (int i = n; i < k; i++)T[i+k] = {-1, INF};
for (int i = k-1; i; i--)T[i] = {max(T[2*i].max, T[2*i+1].max), min(T[2*i].min, T[2*i+1].min)};
}
ll lower_right(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a destra di valore minore di v
if (T[i].min >= v)return -1;
if (l >= y || r <= x)return -1;
if (r == l+1)return l;
ll t = lower_right(2*i+1, x, y, l, (l+r)>>1, v);
if (t != -1)return t;
return lower_right(2*i, x, y, (l+r)>>1, r, v);
}
ll lower_left(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a sinistra di valore minore di v
if (T[i].min >= v)return -1;
if (l >= y || r <= x)return -1;
if (r == l+1)return l;
ll t = lower_left(2*i, x, y, (l+r)>>1, r, v);
if (t != -1)return t;
return lower_left(2*i+1, x, y, l, (l+r)>>1, v);
}
ll upper_left(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a sinistra di valore maggiore di v
if (T[i].max <= v)return -1;
if (l >= y || r <= x)return -1;
if (r == l+1)return l;
ll t = upper_left(2*i, x, y, (l+r)>>1, r, v);
if (t != -1)return t;
return upper_left(2*i+1, x, y, l, (l+r)>>1, v);
}
ll upper_right(ll i, ll x, ll y, ll l, ll r, ll v){ // trova il punto più a destra di valore maggiore di v
if (T[i].max <= v)return -1;
if (l >= y || r <= x)return -1;
if (r == l+1)return l;
ll t = upper_right(2*i+1, x, y, l, (l+r)>>1, v);
if (t != -1)return t;
return upper_right(2*i, x, y, (l+r)>>1, r, v);
}
vector <ll> order;
void dfs(ll c, vector <ll> g[], vector <bool> &vis){
if (vis[c])return;
vis[c] = 1;
order.push_back(c);
for (auto x : g[c])dfs(x, g, vis);
}
void dfs_l(ll c, vector <ll> g[], vector <bool> &vis, ll r){
if (c > r)return;
if (vis[c])return;
vis[c] = 1;
for (auto x : g[c])dfs_l(c, g, vis, r);
}
void dfs_r(ll c, vector <ll> g[], vector <bool> &vis, ll l){
if (c < l)return;
if (vis[c])return;
vis[c] = 1;
for (auto x : g[c])dfs_r(c, g, vis, l);
}
vector <int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
vector <ll> g[N];
for (int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector <int> sol;
if (N <= 3000 && X.size() <= 6000 && S.size() <= 3000){
for (int t = 0; t < S.size(); t++){
ll s = S[t], e = E[t], l = L[t], r = R[t];
vector <bool> reachable_l(N, 0), reachable_r(N, 0);
dfs_l(s, g, reachable_l, r);
dfs_r(e, g, reachable_r, l);
for (int i = 0; i < N; i++){
if (reachable_l[i] && reachable_r[i]){
sol.push_back(1);
goto next;
}
}
sol.push_back(0);
next:
}
return sol;
}
for (int i = 0; i < N; i++){
if (g[i].size() == 1){
vector <bool> vis(N, 0);
dfs(i, g, vis);
break;
}
}
build(N, order);
vector <int> pos(N);
for (int i = 0; i < N; i++)pos[order[i]] = i;
for (int t = 0; t < S.size(); t++){
ll s = S[t], e = E[t], l = L[t], r = R[t];
if (pos[s] < pos[e]){
ll x = lower_right(1, pos[s], pos[e]+1, 0, k, l), y = upper_left(1, pos[s], pos[e]+1, 0, k, r);
if (x == -1 || y == -1 || x < y)sol.push_back(1);
else sol.push_back(0);
}
else {
ll x = upper_right(1, pos[e], pos[s]+1, 0, k, l), y = lower_left(1, pos[e], pos[s]+1, 0, k, r);
if (x == -1 || y == -1 || x < y)sol.push_back(1);
else sol.push_back(0);
}
}
return sol;
}
Compilation message
werewolf.cpp: In function 'void dfs_l(ll, std::vector<long long int>*, std::vector<bool>&, ll)':
werewolf.cpp:73:15: warning: unused variable 'x' [-Wunused-variable]
73 | for (auto x : g[c])dfs_l(c, g, vis, r);
| ^
werewolf.cpp: In function 'void dfs_r(ll, std::vector<long long int>*, std::vector<bool>&, ll)':
werewolf.cpp:80:15: warning: unused variable 'x' [-Wunused-variable]
80 | for (auto x : g[c])dfs_r(c, g, vis, l);
| ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int t = 0; t < S.size(); t++){
| ~~^~~~~~~~~~
werewolf.cpp:106:9: error: expected primary-expression before '}' token
106 | }
| ^
werewolf.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int t = 0; t < S.size(); t++){
| ~~^~~~~~~~~~
