#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
vector<int>graph,rev;
vector<int>tree[200001];
int nb;
int indexi[200001],indexi1[200001];
int segtree[800001],segtree1[800001],segtree2[800001],segtree3[800001];
void dfs(int node,int p)
{
indexi[node]=graph.size();
indexi1[node]=nb-1-graph.size();
graph.pb(node);
for(auto it:tree[node]){
if(it!=p)
dfs(it,node);
}
}
void build(int index,int l,int r,int yo)
{
if(l==r)
{
if(!yo)
segtree[index]=graph[l];
else
segtree2[index]=rev[l];
return;
}
int mid =(l+r)/2;
build(index*2,l,mid,yo);
build(index*2+1,mid+1,r,yo);
if(!yo)
{
if(segtree[index*2]<segtree[index*2+1])
segtree[index]=segtree[index*2];
else segtree[index]=segtree[index*2+1];
}
else
{
if(segtree2[index*2]<segtree2[index*2+1])
segtree2[index]=segtree2[index*2];
else segtree2[index]=segtree2[index*2+1];
}
}
void build1(int index,int l,int r,int yo)
{
if(l==r)
{
if(!yo)
segtree1[index]=graph[l];
else
segtree3[index]=rev[l];
return;
}
int mid =(l+r)/2;
build1(index*2,l,mid,yo);
build1(index*2+1,mid+1,r,yo);
if(!yo)
{
if(segtree1[index*2]>segtree1[index*2+1])
segtree1[index]=segtree1[index*2];
else segtree1[index]=segtree1[index*2+1];
}
else
{
if(segtree3[index*2]>segtree3[index*2+1])
segtree3[index]=segtree3[index*2];
else segtree3[index]=segtree3[index*2+1];
}
}
int query(int in,int l,int r,int x,int y,int val,int yo)
{
if(l>y || x>r)return INF;
/*else if(l>=x && r<=y)
{
if(!yo)
{if(segtree[in]<val && l==r)
return segtree[in];
else if(segtree[in]>=val)
return INF;}
else
{
if(segtree2[in]<val && l==r)
return segtree2[in];
else if(segtree2[in]>=val)
return INF;
}
}*/
if(!yo && segtree[in]>=val)return INF;
if(yo!=0 && segtree2[in]>=val)return INF;
if(l==r && !yo)return segtree[in];
if(l==r && yo==1)return segtree2[in];
int mid = (l+r)/2;
////debugs(l,r);
////debug(mid);
int fal = query(in*2+1,mid+1,r,x,y,val,yo);
if(fal!=INF)return fal;
return query(in*2,l,mid,x,y,val,yo);
}
int query1(int in,int l,int r,int x,int y,int val,int yo)
{
////debugs(l,r);
if(l>y || x>r)return -INF;
/*else if(l>=x && r<=y && l==r)
{
if(!yo)
{if(segtree1[in]>val && l==r)
return segtree1[in];
else if(segtree1[in]<=val)
return -INF;}
else if(yo)
{
if(segtree3[in]>val && l==r)
return segtree3[in];
else if(segtree3[in]<=val)
return -INF;
}
}*/
////debugs(l,r);
if(!yo && segtree1[in]<=val)return -INF;
if(yo!=0 && segtree3[in]<=val)return -INF;
if(l==r && !yo)return segtree1[in];
if(l==r && yo==1)return segtree3[in];
int mid = (l+r)/2;
int fal = query1(in*2,l,mid,x,y,val,yo);
if(fal!=-INF)return fal;
return query1(in*2+1,mid+1,r,x,y,val,yo);
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
nb=N;
vector<int>ans;
ans.resize(S.size());
for (int i = 0; i < X.size(); ++i)
{
int node1=X[i],node2=Y[i];
tree[node1].pb(node2);
tree[node2].pb(node1);
}
for (int i = 0; i < N; ++i)
{
if(tree[i].size()==1){dfs(i,-1);break;}
}
rev=graph;
reverse(rev.begin(),rev.end());
build(1,0,graph.size()-1,0);
build(1,0,graph.size()-1,1);
build1(1,0,graph.size()-1,0);
build1(1,0,graph.size()-1,1);
//debug(1);
for (int i = 0; i < E.size(); ++i)
{
int hey = indexi[S[i]];
int dey = indexi[E[i]];
////debugs(hey,dey);
//debugs(hey,dey);
bool ka=true;
if(hey<dey)
{
int fir = query(1,0,graph.size()-1,hey,dey,L[i],0);
////debug(fir);
int sec = query1(1,0,graph.size()-1,hey,dey,R[i],0);
////debugs(fir,sec);
int ind=0,ind2=0;
if(fir!=INF)
ind = indexi[fir];
if(sec!=-INF)
ind2 = indexi[sec];
if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
else if(fir!=INF && ind==dey)ka=false;
else if(sec!=-INF && ind2==hey)ka=false;
////debugs(ind2,hey);
ans[i]=ka;
}
else
{
int fir = query(1,0,graph.size()-1,nb-1-hey,nb-1-dey,L[i],1);
int sec = query1(1,0,graph.size()-1,nb-1-hey,nb-1-dey,R[i],1);
////debugs(fir,sec);
int ind=0,ind2=0;
if(fir!=INF)
ind = indexi1[fir];
if(sec!=-INF)
ind2 = indexi1[sec];
if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
else if(fir!=INF && ind==(nb-1-dey))ka=false;
else if(sec!=-INF && ind2==(nb-1-hey))ka=false;
ans[i]=ka;
}
}
return ans;
}
//code the AC sol !
// BS/queue/map
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:152:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); ++i)
~~^~~~~~~~~~
werewolf.cpp:169:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E.size(); ++i)
~~^~~~~~~~~~
werewolf.cpp:201:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(sec!=-INF)
^~
werewolf.cpp:203:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(fir!=INF && sec!=-INF && (ind-ind2)>=-1)ka=false;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
572 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
572 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
531 ms |
42348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
572 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
