#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<vector<int> > adj;
vector<int> le,ri,ind;
int smin[800001][26],smax[800001][26];
void build(int tab[],int n)
{
for (int x=0;x<n;x++)
{
smin[x][0]=tab[x];
smax[x][0]=tab[x];
}
for (int y=1;y<26;y++)
{
for (int x=0;(x+(1<<y)-1)<n;x++)
{
smin[x][y]=min(smin[x][y-1],smin[x+(1<<(y-1))][y-1]);
smax[x][y]=max(smax[x][y-1],smax[x+(1<<(y-1))][y-1]);
}
}
}
int maxn(int l,int r)
{
int x=(int)log2(r-l+1);
return max(smax[l][x],smax[r-(1<<x)+1][x]);
}
int minn(int l,int r)
{
int x=(int)log2(r-l+1);
return min(smin[l][x],smin[r-(1<<x)+1][x]);
}
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();
adj.resize(n+1);
le.resize(n+1);
ri.resize(n+1);
ind.resize(n+1);
for(int a=0;a<n;a++)
ind[a]=-1;
for(int a=0;a<m;a++)
{
adj[x[a]].push_back(y[a]);
adj[y[a]].push_back(x[a]);
}
int a=0,b=0;
for(a=0;a<n;a++)
{
if(adj[a].size()==1)
break;
}
for(b=0;b<n;b++)
{
if(adj[b].size()==1 && b!=a)
break;
}
ind[a]=0;
int cur=a;
while(cur!=b)
{
if(ind[adj[cur][0]]==-1)
ind[adj[cur][0]]=ind[cur]+1,cur=adj[cur][0];
else
ind[adj[cur][1]]=ind[cur]+1,cur=adj[cur][1];
}
vector<int> ans;
ans.resize(q);
int tab[n];
for(int z=0;z<n;z++)
tab[ind[z]]=z;
build(tab,n);
for(int z=0;z<q;z++)
{
int d=0;
if(ind[e[z]]>ind[s[z]])
{
if(minn(ind[s[z]],ind[e[z]])>r[z] || maxn(ind[s[z]],ind[e[z]])<l[z])
d=0;
else
{
int se=ind[s[z]],re=ind[e[z]];
while(re>se)
{
int mid=(se+re)/2;
if(minn(ind[s[z]],mid)>=l[z])
se=mid;
else
re=mid-1;
}
if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(se,ind[e[z]])<=r[z])
d=1;
else
d=0;
}
}
else
{
if(minn(ind[e[z]],ind[s[z]])>r[z] || maxn(ind[e[z]],ind[s[z]])<l[z])
d=0;
else
{
int se=ind[e[z]],re=ind[s[z]];
while(re>se)
{
int mid=(se+re)/2;
if(minn(mid,ind[s[z]])>=l[z])
re=mid;
else
se=mid+1;
}
if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(ind[e[z]],se)<=r[z])
d=1;
else
d=0;
}
}
ans[z]=d;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4056 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4056 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4101 ms |
66252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4056 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
