#pragma GCC optimize("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define INF (int)(1e9)
vector<vector<int> > vec;
int A[200005],idx=0,to_id[200005];
ii st[800005];
bool vis[200005];
void build(int node,int l,int r){
if(l==r){
st[node]=ii(A[l],A[l]);
return ;
}
int med=((l+r)>>1);
build(node<<1,l,med),build((node<<1)+1,med+1,r);
st[node].fi=min(st[node<<1].fi,st[(node<<1)+1].fi);
st[node].se=max(st[node<<1].se,st[(node<<1)+1].se);
}
ii query(int node,int l,int r,int i,int j){
if(l>j||r<i)
return ii(INF,-1);
if(l>=i&&r<=j)
return st[node];
int med=((l+r)>>1);
ii q1=query(node<<1,l,med,i,j),q2=query((node<<1)+1,med+1,r,i,j);
return ii(min(q1.fi,q2.fi),max(q1.se,q2.se));
}
int D,LE,RE;
int vis_dfs[5001],v=1;
int dfs(int node,int changed,int trans){
//cerr<<node<<" "<<changed<<" "<<trans<<"\n";
if(node==D&&changed)return 1;
if(node==D&&!changed)return 0;
vis_dfs[node]=v;
int ans=0;
for(auto child:vec[node]){
if(vis_dfs[child]==v)continue;
if(child<LE&&!changed){
if(trans)dfs(child,1,1);
else continue;
}
if(child>RE&&changed)continue;
ans|=dfs(child,changed,trans|(child>=LE&&child<=RE));
if((trans|(child>=LE&&child<=RE))&&child<=RE)ans|=dfs(child,1,1);
if(ans){vis_dfs[node]=v-1; return 1;}
}
vis_dfs[node]=v-1;
return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int M = X.size();
int Q = S.size();
vec.resize(N);
for (int i = 0; i < X.size(); ++i)
{
vec[X[i]].pb(Y[i]);
vec[Y[i]].pb(X[i]);
}
if(N<=100||M<=200||Q<=100){
vector<int> res(Q);
for (int i = 0; i < Q; ++i)
{
D=E[i];
LE=L[i],RE=R[i];
res[i]=dfs(S[i],0,(S[i]>=L[i]&&S[i]<=R[i]));
v++;
}
return res;
}
int start=0;
for (int i = 0; i < N; ++i)
if(vec[i].size()==1){
start=i;
break;
}
queue<int> AA;
AA.push(start);
vis[start]=1;
while(!AA.empty()){
int front=AA.front();
A[idx]=front;
to_id[front]=idx++;
AA.pop();
for(auto child:vec[front])
if(!vis[child])
vis[child]=1,AA.push(child);
}
build(1,0,idx);
vector<int> res(Q);
fill(res.begin(),res.end(),0);
for (int i = 0; i < Q; ++i) {
if(S[i]==E[i]){
if(S[i]<=R[i]&&S[i]>=L[i])res[i]=1;
else res[i]=0;
continue;
}
if(S[i]<L[i]||E[i]>R[i]){res[i]=0;continue;}
if(to_id[S[i]]<to_id[E[i]]){
int l=to_id[S[i]],r=to_id[E[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,to_id[S[i]],med-1);
if(q.fi<L[i]){r=med-1;continue;}
}
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,med+1,to_id[E[i]]);
if(q.se>R[i]){l=med+1;continue;}
}
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]>=L[i]){
if(A[med]==(E[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]<=R[i]){
if(A[med]==S[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}
else{
int l=to_id[E[i]],r=to_id[S[i]];
while(l<=r){
int med=((l+r)>>1);
if(med!=to_id[E[i]]){
ii q=query(1,0,idx,to_id[E[i]],med-1);
if(q.se>R[i]){r=med-1;continue;}
}
if(med!=to_id[S[i]]){
ii q=query(1,0,idx,med+1,to_id[S[i]]);
if(q.fi<L[i]){l=med+1;continue;}
}
if(A[med]<=R[i]&&A[med]>=L[i])res[i]=1;
else if(A[med]<=R[i]){
if(A[med]==(S[i]))res[i]=0;
else if(A[med+1]<=R[i]&&A[med+1]>=L[i])res[i]=1;
else res[i]=0;
}
else if(A[med]>=L[i]){
if(A[med]==E[i])res[i]=0;
else if(A[med-1]<=R[i]&&A[med-1]>=L[i])res[i]=1;
else res[i]=0;
}
break;
}
}}
return res;
}
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:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); ++i)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1389 ms |
32056 KB |
Output is correct |
| 2 |
Correct |
541 ms |
32072 KB |
Output is correct |
| 3 |
Correct |
572 ms |
30864 KB |
Output is correct |
| 4 |
Correct |
933 ms |
30712 KB |
Output is correct |
| 5 |
Correct |
1045 ms |
30840 KB |
Output is correct |
| 6 |
Correct |
1645 ms |
30868 KB |
Output is correct |
| 7 |
Correct |
1616 ms |
30732 KB |
Output is correct |
| 8 |
Correct |
483 ms |
30712 KB |
Output is correct |
| 9 |
Correct |
533 ms |
30840 KB |
Output is correct |
| 10 |
Correct |
606 ms |
30764 KB |
Output is correct |
| 11 |
Correct |
873 ms |
30712 KB |
Output is correct |
| 12 |
Correct |
1128 ms |
30840 KB |
Output is correct |
| 13 |
Correct |
1235 ms |
30772 KB |
Output is correct |
| 14 |
Correct |
1235 ms |
30792 KB |
Output is correct |
| 15 |
Correct |
1244 ms |
30756 KB |
Output is correct |
| 16 |
Correct |
1188 ms |
30840 KB |
Output is correct |
| 17 |
Correct |
1618 ms |
30864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
