#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pairll;
#define pb push_back
#define N 100007
#define fr first
#define sc second
ll n,a[8*N],b[8*N],d[2*N],k[2*N];
vector<ll>v[2*N];
vector<int>res;
void S1(ll x,ll y){
k[x]=k[y]+1;
d[k[x]]=x;
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=y)S1(v[x][i],x);
}
return ;
}
void BT(ll x,ll l,ll r){
if(l==r){
a[x]=d[l];
b[x]=d[l];
return ;
}
ll m1=(l+r)/2;
BT(x*2+1,l,m1);
BT(x*2+2,m1+1,r);
a[x]=min(a[x*2+1],a[x*2+2]);
b[x]=max(b[x*2+1],b[x*2+2]);
return ;
}
ll R1(ll x,ll l,ll r,ll tl,ll tr){
if(r<tl || tr<l)return n;
if(tl<=l && r<=tr)return a[x];
ll m1=(l+r)/2;
return min(R1(x*2+1,l,m1,tl,tr),R1(x*2+2,m1+1,r,tl,tr));
}
ll R2(ll x,ll l,ll r,ll tl,ll tr){
if(r<tl || tr<l)return 0;
if(tl<=l && r<=tr)return b[x];
ll m1=(l+r)/2;
return max(R2(x*2+1,l,m1,tl,tr),R2(x*2+2,m1+1,r,tl,tr));
}
std::vector<int> check_validity(int N1, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
n=N1;
for(int i=0;i<X.size();i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
for(int i=0;i<n;i++){
if(v[i].size()==1){
S1(i,i);
break;
}
}
for(int i=0;i<n;i++){
//cout<<k[i]<<" "<<i<<endl;
}
BT(0,1,n);
for(int i=0;i<S.size();i++){
ll x=S[i];
ll y=E[i];
if(k[x]<k[y]){
ll l=k[x];
ll r=k[y];
while(l<r){
ll m1=(l+r+1)/2;
if(R1(0,1,n,k[x],m1)>=L[i])l=m1;
else r=m1-1;
}
if(R1(0,1,n,k[x],l)>=L[i] && R2(0,1,n,l,k[y])<=R[i])res.pb(1);
else res.pb(0);
// cout<<l<<" "<<R1(0,1,n,k[x],l)<<" "<<R2(0,1,n,l,k[y])<<endl;
}else{
ll l=k[y];
ll r=k[x];
while(l<r){
ll m1=(l+r)/2;
if(R1(0,1,n,m1,k[x])>=L[i])r=m1;
else l=m1+1;
}
if(R1(0,1,n,l,k[x])>=L[i] && R2(0,1,n,k[y],l)<=R[i])res.pb(1);
else res.pb(0);
//cout<<l<<" "<<R1(0,1,n,l,k[x])<<" "<<R2(0,1,n,k[y],l)<<endl;
}
}
return res;
}
Compilation message
werewolf.cpp: In function 'void S1(ll, ll)':
werewolf.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
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:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
138 ms |
210140 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
138 ms |
210140 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
946 ms |
43064 KB |
Output is correct |
2 |
Correct |
1064 ms |
43228 KB |
Output is correct |
3 |
Correct |
1053 ms |
43116 KB |
Output is correct |
4 |
Correct |
1022 ms |
43124 KB |
Output is correct |
5 |
Correct |
1020 ms |
43084 KB |
Output is correct |
6 |
Correct |
987 ms |
43036 KB |
Output is correct |
7 |
Correct |
1065 ms |
43140 KB |
Output is correct |
8 |
Correct |
1047 ms |
43080 KB |
Output is correct |
9 |
Correct |
496 ms |
43008 KB |
Output is correct |
10 |
Correct |
600 ms |
43096 KB |
Output is correct |
11 |
Correct |
710 ms |
43120 KB |
Output is correct |
12 |
Correct |
717 ms |
43096 KB |
Output is correct |
13 |
Correct |
1047 ms |
43192 KB |
Output is correct |
14 |
Correct |
1018 ms |
43148 KB |
Output is correct |
15 |
Correct |
1035 ms |
43040 KB |
Output is correct |
16 |
Correct |
1078 ms |
43036 KB |
Output is correct |
17 |
Correct |
1058 ms |
43096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
138 ms |
210140 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |