#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int m,q,h[200005],mini[200005][20],maxi[200005][20],cnt;
vector<int>g[200005],sol;
bool viz[200005],na[200005],v[200005],ok;
void dfs(int nod,int t)
{
viz[nod]=1;
for(auto it:g[nod]){
if (viz[it]==0 && it<=t)
dfs(it,t);
}
}
void dfs2(int nod,int t)
{
na[nod]=1;
for(auto it:g[nod]){
if (na[it]==0 && it>=t)
dfs2(it,t);
}
}
void dfs3(int nod)
{
v[nod]=1;
mini[cnt][0]=nod;
maxi[cnt][0]=nod;
h[nod]=cnt;
cnt++;
for(auto it:g[nod])
if (v[it]==0)
dfs3(it);
}
vector<int> check_validity(int n,vector<int>x,vector<int>y,vector<int>s,vector<int>e,vector<int>l,vector<int>r)
{
m=x.size();
q=s.size();
int i;
for(i=0;i<m;i++)
g[x[i]].push_back(y[i]),g[y[i]].push_back(x[i]);
if (n<=3000 && q<=3000){
for(i=0;i<q;i++){
ok=0;
int j;
for(j=0;j<n;j++)
viz[j]=0,na[j]=0;
dfs(e[i],r[i]);
dfs2(s[i],l[i]);
for(j=0;j<n;j++)
if (viz[j] && na[j])
ok=1;
sol.push_back(ok);
}
return sol;
}
for(i=0;i<n;i++)
if (v[i]==0 && g[i].size()==1)
dfs3(i);
for(j=1;j<20;j++)
for(i=0;i<n;i++){
int auxi=min(n-1,i+(1<<(j-1)));
mini[i][j]=min(mini[i][j-1],mini[auxi][j-1]);
maxi[i][j]=max(maxi[i][j-1],maxi[auxi][j-1]);
}
for(i=0;i<q;i++){
int a=h[s[i]],b=h[e[i]];
if (a<b){
for(j=19;j>=0;j--)
if (a<n && mini[a][j]>=l[i])
a=a+(1<<j);
for(j=19;j>=0;j--){
int x=max(0,b-(1<<j)+1);
if (maxi[x][j]<=r[i])
b=x-1;
}
if (a>=n || b==-1 || a-b>1)
sol.push_back(1);
else
sol.push_back(0);
}
else{
for(j=19;j>=0;j--)
if (b<n && maxi[b][j]<=r[i])
b+=(1<<j);
for(j=19;j>=0;j--){
int x=max(0,a-(1<<j)+1);
if (mini[x][j]>=l[i])
a=x-1;
}
if (b>=n || a==-1 || b-a>1)
sol.push_back(1);
else
sol.push_back(0);
}
}
return sol;
}
Compilation message
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:59:9: error: 'j' was not declared in this scope
59 | for(j=1;j<20;j++)
| ^
werewolf.cpp:68:17: error: 'j' was not declared in this scope
68 | for(j=19;j>=0;j--)
| ^
werewolf.cpp:71:17: error: 'j' was not declared in this scope
71 | for(j=19;j>=0;j--){
| ^
werewolf.cpp:82:17: error: 'j' was not declared in this scope
82 | for(j=19;j>=0;j--)
| ^
werewolf.cpp:85:17: error: 'j' was not declared in this scope
85 | for(j=19;j>=0;j--){
| ^
