#include "werewolf.h"
#include <iostream>
using namespace std;
long long int ma[400005],t[400005][3],road[200005],map[400005][2],tag[200005][2],pointsum[200005],mintree[500005],maxtree[500005],st,en;
int buildmin(int s,int e,int t)
{
if(s==e)return mintree[t]=ma[s];
else return mintree[t]=min(buildmin(s,(s+e)/2,t*2),buildmin((s+e)/2+1,e,t*2+1));
}
int buildmax(int s,int e,int t)
{
if(s==e)return mintree[t]=ma[s];
else return maxtree[t]=max(buildmax(s,(s+e)/2,t*2),buildmax((s+e)/2+1,e,t*2+1));
}
int findmin(int s,int e,int t)
{
if(en<s || st>e)return 99999999;
else if(st<=s && e<=en)return mintree[t];
else return min(findmin(s,(s+e)/2,t*2),findmin((s+e)/2+1,e,t*2+1));
}
int findmax(int s,int e,int t)
{
if(en<s || st>e)return -1;
else if(st<=s && e<=en)return maxtree[t];
else return max(findmax(s,(s+e)/2,t*2),findmax((s+e)/2+1,e,t*2+1));
}
std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,std::vector<int> s, std::vector<int> e,std::vector<int> l, std::vector<int> r) {
int q = s.size();
int m = x.size();
std::vector<int> a(q);
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
pointsum[x[i]]++;
pointsum[y[i]]++;
map[i*2][0]=x[i];
map[i*2][1]=road[y[i]];
road[y[i]]=i*2;
map[i*2+1][0]=y[i];
map[i*2+1][1]=road[x[i]];
road[x[i]]=i*2+1;
}
int one=0,two=0,start=-1,end=-1;
for(int i=0;i<n;i++)
{
if(pointsum[i]==1)
{
one++;
if(start==-1)start=i;
else end=i;
}
if(pointsum[i]==2)two++;
}
//cout<<endl;
if(one==2 && two+one==n && n==m+1)
{
int question=q;
int tag[200005];
int q=road[start];
ma[1]=start;
tag[start]=1;
for(int i=2;i<=n;i++)
{
if(tag[map[q][0]]==0)
{
tag[map[q][0]]=i;
ma[i]=map[q][0];
q=road[map[q][0]];
}
else
{
q=map[q][1];
tag[map[q][0]]=i;
ma[i]=map[q][0];
q=road[map[q][0]];
}
}
buildmin(1,n,1);
buildmax(1,n,1);
for(int i=0;i<question;i++)
{
st=tag[s[i]],en=tag[e[i]];
if(st>en)swap(st,en);
int tmpstart=st,tmpend=en;
int left=st,right=en;
while(left<=right)
{
int mid=(left+right)/2;
st=tmpstart;
en=mid;
//cout<<"找最小"<<st<<" "<<en<<" "<<endl;
int mi=findmin(1,n,1);
en=tmpend;
st=mid;
//cout<<"找最大"<<st<<" "<<en<<" "<<endl;
int ma=findmax(1,n,1);
// cout<<mi<<" "<<ma<<endl;
//cout<<"ok"<<endl;
if(mi>=l[i] && ma<=r[i])
{
a[i]=1;
break;
}
else if(mi<l[i])right=mid-1;
else left=mid+1;
}
//cout<<i<<endl;
}
//cout<<"finish"<<endl;
return a;
}
int ans;
for(int i=0;i<q;i++)
{
ans=0;
for(int j=0;j<n;j++)
{
tag[j][0]=0;
tag[j][1]=0;
}
int people=l[i],wolf=r[i],start=s[i],end=e[i];
tag[start][0]=1;
t[1][0]=start;
t[1][1]=0;
t[1][2]=-1;
int p=1,pp=1;
while(p<=pp)
{
int now=t[p][0],mode=t[p][1];
int g=road[now];
if(now==45 && mode==1 && i==55)
{
int z=p;
while(z!=-1)
{
z=t[z][2];
}
}
if(now<=wolf && now>=people && t[p][1]==0 && tag[now][1]==0)
{
pp++;
t[pp][0]=now;
t[pp][1]=1;
t[pp][2]=p;
tag[now][1]=1;
}
while(g!=-1)
{
if(tag[map[g][0]][mode]==0 && ((mode==0 && map[g][0]>=people) || (mode==1 && map[g][0]<=wolf)))
{
pp++;
t[pp][0]=map[g][0];
t[pp][1]=mode;
t[pp][2]=p;
tag[map[g][0]][mode]=1;
}
g=map[g][1];
}
p++;
}
a[i]=tag[end][1];
}
return a;
}
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:43:27: warning: variable 'end' set but not used [-Wunused-but-set-variable]
int one=0,two=0,start=-1,end=-1;
^~~
werewolf.cpp:113:6: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
int ans;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
233 ms |
36608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
