This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;
const int N=200090;
int idx[N],vis[N],a[N],treemn[N*4],treemx[N*4];
vector<int>v[N];
void go (int x,int y)
{
idx[x]=y;
a[y]=x;
vis[x]=1;
for(auto it:v[x])
{
if(vis[it])continue;
go(it,y+1);
}
}
int get1 (int ind,int st,int end,int l,int r,int x)
{
if(l>end||r<st)return (end-st+1);
int m=(st+end )/2;
int re=0;
if(l<=st&&end<=r)
{
if(st==end&&a[st]<=x)
return 1;
else if(st==end)return 0;
if(treemx[ind*2+1]<=x)
{
re=get1(ind*2+2,m+1,end,l,r,x);
re+=m+1-st;
return re;
}
re=get1(ind*2+1,st,m,l,r,x);
return re;
}
re=get1(ind*2+1,st,m,l,r,x);
if(re==m+1-st)
{
re+=get1(ind*2+2,m+1,end,l,r,x);
return re;
}
return re;
}
int get (int ind,int st,int end,int l,int r,int x)
{
if(l>end||r<st)return (end-st+1);
int m=(st+end )/2;
int re=0;
if(l<=st&&end<=r)
{
if(st==end&&a[st]>=x)
return 1;
else if(st==end)return 0;
if(treemn[ind*2+1]>=x)
{
re=get(ind*2+2,m+1,end,l,r,x);
re+=m+1-st;
return re;
}
re=get(ind*2+1,st,m,l,r,x);
return re;
}
re=get(ind*2+1,st,m,l,r,x);
if(re==m+1-st)
{
re+=get(ind*2+2,m+1,end,l,r,x);
return re;
}
return re;
}
void build(int ind,int st,int end)
{
if(st==end)
{
treemx[ind]=a[st];
treemn[ind]=a[st];return;
}
int m=(st+end)/2;
build(ind*2+1,st,m);
build(ind*2+2,m+1,end);
treemn[ind]=min(treemn[ind*2+1],treemn[ind*2+2]);
treemx[ind]=max(treemx[ind*2+1],treemx[ind*2+2]);
}
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++)
{
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
int st=0;
for(int i=0;i<n;i++)
{
if(v[i].size()==1)st=i;
}
vector<int>ans;
ans.clear();
go(st,1);
build(0,1,n);
int q=S.size();
for(int i=0;i<q;i++)
{
int s=S[i],e=E[i],l=L[i],r=R[i];
if(s<l||e>r)
{
ans.pb(0);continue;
}
if(idx[s]>idx[e])
{
swap(s,e);
int x=get1(0,1,n,idx[s],n,l);
if(x>=idx[e]){ans.pb(1);continue;}
x+=get(0,1,n,x,n,r);
if(x>=idx[e])ans.pb(1);
else ans.pb(0);
continue;
}
int x=get(0,1,n,idx[s],n,l);
if(x>=idx[e]){ans.pb(1);continue;}
x+=get1(0,1,n,x,n,r);
if(x>=idx[e])ans.pb(1);
else ans.pb(0);
}
return ans;
}
/*
5 4 2
1 0
2 1
0 3
3 4
4
1
2
2
*/
Compilation message (stderr)
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:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0;i<X.size();i++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |