#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
int n;
int segtree[nax*4][2];
int tab[nax];
void build(int pos,int l,int r){
if(l==r){
segtree[pos][0]=segtree[pos][1]=tab[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
int query0(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return 1e9;
if(l>=left&&r<=right) return segtree[pos][0];
int mid=(r+l)/2;
return min(query0(pos*2+1,l,mid,left,right),query0(pos*2+2,mid+1,r,left,right));
}
int query1(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return -1e9;
if(l>=left&&r<=right) return segtree[pos][1];
int mid=(r+l)/2;
return max(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int bs_min_left(int x,int cur){
int l=-1;
int r=x;
while(r-l>1){
int mid=(r+l)/2;
if (query0(0,0,n-1,mid,x)>=cur)
r=mid;
else l=mid;
}
return r;
}
int bs_min_right(int x,int cur){
int l=x;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if (query0(0,0,n-1,x,mid)>=cur)
l=mid;
else r=mid;
}
return l;
}
int bs_max_left(int x,int cur){
int l=-1;
int r=x;
while(r-l>1){
int mid=(r+l)/2;
if (query1(0,0,n-1,mid,x)<=cur)
r=mid;
else l=mid;
}
return r;
}
int bs_max_right(int x,int cur){
int l=x;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if (query1(0,0,n-1,x,mid)<=cur)
l=mid;
else r=mid;
}
return l;
}
set<int> mergesort[nax*4];
void build_mergesort(int pos,int l,int r){
if(l==r){
mergesort[pos].insert(tab[l]);
return;
}
int mid=(r+l)/2;
build_mergesort(pos*2+1,l,mid);
build_mergesort(pos*2+2,mid+1,r);
for(auto u:mergesort[pos*2+1]) mergesort[pos].insert(u);
for(auto u:mergesort[pos*2+2]) mergesort[pos].insert(u);
return;
}
bool query(int pos,int l,int r,int left,int right,pair<int,int> cur){
if(l>r||l>right||r<left) return 0;
if(l>=left&&r<=right){
return *mergesort[pos].lower_bound(cur.fi)<=cur.se;
}
int mid=(r+l)/2;
return query(pos*2+1,l,mid,left,right,cur)|query(pos*2+2,mid+1,r,left,right,cur);
}
int t=0;
int conv[nax];
void dfs(int x,int p){
conv[x]=t;
tab[t++]=x;
for(auto u:adj[x]){
if(u==p) continue;
dfs(u,x);
}
return;
}
void min_djikastra(int x){
priority_queue<int> pq;
pq.push(x);
mn[x]=x;
vis[x]=true;
while(!pq.empty()){
int node=pq.top();
pq.pop();
for(auto u:adj[node]){
if(vis[u]) continue;
vis[u]=true;
mn[u]=min(u,mn[node]);
pq.push(u);
}
}
}
vector<int> mn(nax);
vector<int> mx(nax);
bool vis[nax];
void max_djikastra(int x){
priority_queue<int,vector<int>,greater<int>> pq;
pq.push(x);
mx[x]=x;
vis[x]=true;
while(!pq.empty()){
int node=pq.top();
pq.pop();
for(auto u:adj[node]){
if(vis[u]) continue;
vis[u]=true;
mx[u]=max(u,mx[node]);
pq.push(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) {
if(N<=3e3+5&&M<=6e3+5&&Q<=3e3+5){
n=N;
for (int i = 0; i < (int)X.size(); ++i)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vector<int> ans;
int Q=R.size();
for (int i = 0; i < Q; ++i)
{
for (int j = 0; j < N; ++j)
{
mn[j]=1e9;
mx[j]=-1e9;
vis[j]=0;
}
min_djikastra(S[i]);
for (int i = 0; i < N; ++i)
{
vis[j]=0;
}
max_djikastra(E[i]);
pair<int,int> cur={L[i],R[i]};
bool test=false;
for (int j = L[i]; j < R[i]+1; ++j)
{
if(cur.fi<=mn[j]&&mx[j]<=cur.se){
test=true;
}
if(test) break;
}//cout <<endl;
ans.pb((test==true ? 1 : 0));
}
return ans;
}else{
n=N;
int q=R.size();
int v[n];
memset(v,0,sizeof v);
for (int i = 0; i < n-1; ++i)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
v[X[i]]++;
v[Y[i]]++;
}
int lst;
for (int i = 0; i < n; ++i)
{
if(v[i]==1){
lst=i;
}
}
dfs(lst,-1);
build(0,0,n-1);
build_mergesort(0,0,n-1);
vector<int> ans;
for (int i = 0; i < q; ++i)
{
pair<int,int> cur={L[i],R[i]};
S[i]=conv[S[i]];
E[i]=conv[E[i]];
bool test=(E[i]>=S[i]);
pair<int,int> cnt;
if(test){
int right=bs_min_right(S[i],cur.fi);
int left=bs_max_left(E[i],cur.se);
cnt={right,left};
}else{
int right=bs_min_left(S[i],cur.fi);
int left=bs_max_right(E[i],cur.se);
cnt={left,right};
}
if(cnt.fi<cnt.se){
ans.pb(0);
continue;
}
ans.pb((query(0,0,n-1,cnt.se,cnt.fi,cur)) ? 1 : 0);
}
return ans;
}
}
/*namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
Compilation message
werewolf.cpp: In function 'void min_djikastra(int)':
werewolf.cpp:117:5: error: 'mn' was not declared in this scope; did you mean 'n'?
117 | mn[x]=x;
| ^~
| n
werewolf.cpp:118:5: error: 'vis' was not declared in this scope
118 | vis[x]=true;
| ^~~
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:152:18: error: 'M' was not declared in this scope
152 | if(N<=3e3+5&&M<=6e3+5&&Q<=3e3+5){
| ^
werewolf.cpp:152:28: error: 'Q' was not declared in this scope
152 | if(N<=3e3+5&&M<=6e3+5&&Q<=3e3+5){
| ^
werewolf.cpp:160:13: error: redeclaration of 'int Q'
160 | int Q=R.size();
| ^
werewolf.cpp:152:28: note: '<typeprefixerror>Q' previously declared here
152 | if(N<=3e3+5&&M<=6e3+5&&Q<=3e3+5){
| ^
werewolf.cpp:172:21: error: 'j' was not declared in this scope
172 | vis[j]=0;
| ^
werewolf.cpp:236:1: warning: control reaches end of non-void function [-Wreturn-type]
236 | }
| ^
