#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector
using namespace std;
V<int>g[200005];
int pos[200005],logs[200005],spx[200005][18],spn[200005][18];
int gt_mx(int l,int r){
int lev=logs[r-l+1];
return max(spx[l][lev],spx[r-(1<<lev)+1][lev]);
}
int gt_mn(int l,int r){
int lev=logs[r-l+1];
return min(spn[l][lev],spn[r-(1<<lev)+1][lev]);
}
bool check(int l,int r,int nl,int nr){
if(l>r)swap(l,r);
return gt_mn(l,r)>=nl&>_mx(l,r)<=nr;
}
V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){
int root,i,j;
for(i=2;i<=n;i++)logs[i]=logs[i>>1]+1;
V<int>res;
for(i=0;i+1<n;i++){
x[i]++;
y[i]++;
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
for(i=1;i<=n;i++)if(g[i].size()==1)root=i;
spx[1][0]=root;
spn[1][0]=root;
pos[root]=1;
int p=root;
for(i=2;i<=n;i++){
if(g[root][0]!=p){
p=root;
root=g[root][0];
}else{
p=root;
root=g[root][1];
}
spx[i][0]=root;
spn[i][0]=root;
pos[root]=i;
}
for(j=1;j<18;j++){
for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]);
for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]);
}
for(int i=0;i<S.size();i++){
int l=pos[S[i]+1],r=pos[E[i]+1],s=L[i]+1,e=R[i]+1;
if(l<=r){
int mxl=n,mnr=1;
while(l<mxl){
int mid=(l+mxl+1)>>1;
if(check(pos[S[i]+1],mid,s,n))l=mid;
else mxl=mid-1;
}
while(mnr<r){
int mid=(mnr+r)>>1;
if(check(mid,pos[E[i]+1],1,e))r=mid;
else mnr=mid+1;
}
if(!check(mxl,mxl,s,n))mxl--;
if(!check(mnr,mnr,1,e))mnr++;
res.push_back(mxl>=mnr);
}else{
swap(l,r);
int mxl=n,mnr=1;
while(l<mxl){
int mid=(l+mxl+1)>>1;
if(check(pos[S[i]+1],mid,1,e))l=mid;
else mxl=mid-1;
}
while(mnr<r){
int mid=(mnr+r)>>1;
if(check(mid,pos[E[i]+1],s,n))r=mid;
else mnr=mid+1;
}
if(!check(mxl,mxl,1,e))mxl--;
if(!check(mnr,mnr,s,n))mnr++;
res.push_back(mxl>=mnr);
}
}
return res;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9
/*
1
1
1
0
1
1
0
1
0
1
*/
Compilation message
werewolf.cpp:110:1: warning: "/*" within comment [-Wcomment]
110 | /*
|
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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
werewolf.cpp:31:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
31 | spx[1][0]=root;
| ~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
828 ms |
51640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
