//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb(n) push_back(n)
using namespace std;
const int N= 2*1e5+5;
vector<vector<int>>edges;
//2nd 1st subtask
struct first{
bool reached=0;
int l, h, used1[N],used2[N];
void dfs1(int v){
used1[v]=1;
for(auto x:edges[v]){
if(x<l||used1[x]) continue;
dfs1(x);
}
}
void dfs2(int v){
used2[v]=1;
if(used1[v]&&used2[v]) {
reached=1;
return;
}
if(reached) return;
for(auto x:edges[v]){
if(x>h||used2[x]) continue;
if(reached) return;
dfs2(x);
}
}
};
// 3rd subtask
const int INF=1e9+7;
int root, timer, n, m, q;
vector<int>a(N);
void dfs(int u,int p){
a[u]=timer, timer++;
for(auto x:edges[u]){
if(x == p) continue;
dfs(x, u);
}
}
struct second{
struct node{
int mx,mn;
};
vector<node>tree;
int s;
node ntr={0,INF};
void mtree(int n){
s=1;
while(s<n) s*=2;
tree.assign(s*2, ntr);
for(int i=0;i<n;i++)
tree[a[i]+s]={i, i};
for(int i=s-1;i>0;i--){
tree[i].mn=min(tree[i*2+1].mn, tree[i*2].mn);
tree[i].mx=max(tree[i*2+1].mx, tree[i*2].mx);
}
}
int min_less(int l,int r,int lx,int rx,int x,int low){
if(lx>=r||rx<=l) return INF;
if(lx==rx){
if(lx>=l&&tree[x].mn<low) return lx;
else return INF;
}
int mid=(lx+rx)/2;
if(lx>=l&&rx<=r){
if(tree[x*2].mn<low) return min_less(l,r,lx,mid,x*2,low);
else return min_less(l,r,mid+1,rx,x*2+1,low);
}return min(min_less(l,r,lx,mid,x*2,low),
min_less(l,r,mid+1,rx,x*2+1,low));
}
int min_less1(int l,int low){
return min_less(l, s, 0, s, 1, low);
}
int min_great(int l,int r,int lx,int rx,int x,int low){
if(lx>=r||rx<=l) return INF;
if(lx==rx){
if(lx>=l&&tree[x].mn>low) return lx;
else return INF;
}
int mid=(lx+rx)/2;
if(lx>=l&&rx<=r){
if(tree[x*2].mn>low) return min_great(l,r,lx,mid,x*2,low);
else return min_great(l,r,mid+1,rx,x*2+1,low);
}return min(min_great(l,r,lx,mid,x*2,low),
min_great(l,r,mid+1,rx,x*2+1,low));
}
int min_great1(int l,int low){
return min_great(l,s,0,s,1,low);
}
//======================================================================================================
int max_less(int l,int r,int lx,int rx,int x,int high){
if(lx>=r||rx<=l) return -1;
if(rx==lx){
if(rx<=r && tree[x].mx<high) return lx;
else return -1;
}
int mid=(lx+rx)/2;
if(lx>=l&&rx<=r){
if(tree[x*2+1].mx<high) return max_less(l,r,mid+1,rx,x*2+1,high);
else return max_less(l,r,lx,mid,x*2,high);
}
return max(max_less(l,r,lx,mid,x*2,high), max_less(l,r,mid+1,rx,x*2+1,high));
}
int max_less1(int r,int high){
return max_less(0,r,0,s,0,high);
}
int max_great(int l,int r,int lx,int rx,int x,int high){
if(lx>=r||rx<=l) return -1;
if(rx==lx){
if(rx<=r && tree[x].mx<high) return lx;
else return -1;
}
int mid=(lx+rx)/2;
if(lx>=l&&rx<=r){
if(tree[x*2+1].mx<high) return max_great(l,r,mid+1,rx,x*2+1,high);
else return max_great(l,r,lx,mid,x*2,high);
}
return max(max_great(l,r,lx,mid,x*2,high), max_less(l,r,mid+1,rx,x*2+1,high));
}
int max_great1(int r,int high){
return max_great(0,r,0,s,0,high);
}
};
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,q=S.size(),m=X.size();
edges.resize(n);
for(int i=0;i<m;i++){
edges[X[i]].pb(Y[i]);
edges[Y[i]].pb(X[i]);
}
if(n<3000){
first ans;
a.resize(q);
for(int i=0;i<q;i++){
ans.l=l[i], ans.h=l[i];
if(S[i]>=ans.l)
ans.dfs1(S[i]);
ans.reached=0;
if(E[i]<=ans.h)
ans.dfs2(E[i]);
a[i]=ans.reached;
memset(ans.used1,0,sizeof(ans.used1));
memset(ans.used2,0,sizeof(ans.used2));
}
return a;
}
for(int i=1;i<=n;i++)
if(edges[i].size()==1) root = i;
timer=0;
dfs(root, root);
second stree;
stree.mtree(n);
vector<int>ans(q);
for(int i=0;i<q;i++){
int s=a[S[i]],e=a[E[i]];
ans[i]=1;
if(s<e){
int mnlt_L=stree.min_less1(s,l[i])-1,
mxgt_R=stree.max_great1(e,r[i])+1;
if(mnlt_L<mxgt_R) ans[i]=0;
}else{
int mxlt_L=stree.max_less1(s,l[i])+1;
int mngt_R=stree.min_great1(e,r[i])-1;
if(mxlt_L > mngt_R)ans[i]=0;
}
}
return ans;
}
/*
6 5 3
1 2
2 3
3 4
4 5
0 1
1 3 4 5
1 3 4 5
3 2 4 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
375 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 |
375 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 |
736 ms |
40160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
375 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
