#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int logN=18;
struct node
{
int left_child,right_child,maxval;
};
vector<node>nodes;
vector<int>g[MAXN];
int in_time[2*MAXN][2];
int out_time[2*MAXN][2];
int par[2][MAXN][logN];
int x[MAXN],y[MAXN];
struct tree_2d
{
set<int>s[3*MAXN];
void build(int l,int r,int idx)
{
for(int i=l;i<=r;i++)s[idx].insert(y[i]);
if(l==r)return;
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
}
bool query(int l,int r,int idx,int ql,int qr,int ql1,int qr1)
{
if(l>qr)return 0;
if(r<ql)return 0;
if(l>=ql&&r<=qr)
{
auto it=s[idx].lower_bound(ql1);
if(it!=s[idx].end()&&(*it)<=qr1)return 1;
return 0;
}
int mid=(l+r)/2;
return query(l,mid,idx*2,ql,qr,ql1,qr1)||query(mid+1,r,idx*2+1,ql,qr,ql1,qr1);
}
}tr;
struct dsu
{
int par[2*MAXN];
void init()
{
for(int i=0;i<MAXN;i++)
{
par[i]=i;
}
}
int getRoot(int u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
void join(int p,int q,int f)
{
p=getRoot(p);
q=getRoot(q);
if(p==q)return;
int t=nodes.size();
par[p]=t;par[q]=t;
if(!f)nodes.push_back({p,q,max(nodes[p].maxval,nodes[q].maxval)});
else nodes.push_back({p,q,min(nodes[p].maxval,nodes[q].maxval)});
}
}dsu1;
int t,n;
void dfs(int u,int p,int f)
{
in_time[u][f]=++t;
par[f][u][0]=p;
if(nodes[u].left_child!=-1)dfs(nodes[u].left_child,u,f);
if(nodes[u].right_child!=-1)dfs(nodes[u].right_child,u,f);
out_time[u][f]=t;
}
void precompute()
{
for(int f=0;f<1;f++)
for(int step=1;step<logN;step++)
{
for(int i=0;i<n;i++)
{
if(par[f][i][step-1]==-1)par[f][i][step]=-1;
else par[f][i][step]=par[f][par[f][i][step-1]][step-1];
}
}
}
int lift_left(int vert,int l)
{
if(vert<l)return -1;
for(int j=logN-1;j>=0;j--)
{
if(par[0][vert][j]==-1)continue;
if(nodes[par[0][vert][j]].maxval<l)continue;
vert=par[0][vert][j];
}
return vert;
}
int lift_right(int vert,int r)
{
if(vert>r)return -1;
for(int j=logN-1;j>=0;j--)
{
if(par[1][vert][j]==-1)continue;
if(nodes[par[1][vert][j]].maxval>r)continue;
vert=par[1][vert][j];
}
return vert;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n=N;
for(int i=0;i<X.size();i++)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i=0;i<N;i++)
{
nodes.push_back({-1,-1,i});
}
//cout<<"*0\n";
dsu1.init();
for(int i=N-1;i>=0;i--)
{
//cout<<"%% "<<i<<endl;
for(auto xd:g[i])
{
if(xd>i)
{
dsu1.join(xd,i,0);
}
}
}
t=0;
//cout<<"*0.5\n";
dfs(nodes.size()-1,-1,0);
//cout<<"*1\n";
nodes.clear();
for(int i=0;i<N;i++)
{
nodes.push_back({-1,-1,i});
}
dsu1.init();
for(int i=0;i<N;i++)
{
for(auto xd:g[i])
{
if(xd<i)
{
dsu1.join(xd,i,1);
}
}
}
t=0;
dfs(nodes.size()-1,-1,1);
precompute();
//cout<<"*2\n";
for(int i=0;i<N;i++)
{
x[i]=in_time[i][0];
y[i]=in_time[i][1];
//cout<<x[i]<<" "<<y[i]<<endl;
}
tr.build(1,n,1);
vector<int>ans;
//cout<<"*3\n";
for(int i=0;i<L.size();i++)
{
int t1=lift_left(S[i],L[i]);
int t2=lift_right(E[i],R[i]);
if(t1!=-1&&t2!=-1&&tr.query(1,n,1,in_time[t1][0], out_time[t1][0],in_time[t2][1],out_time[t2][1]))
{
ans.push_back(1);
}
else ans.push_back(0);
}
return ans;
}
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:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<X.size();i++)
| ~^~~~~~~~~
werewolf.cpp:173:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i=0;i<L.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
34004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
34004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
422 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
34004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
