#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> indx;
map<int,int> mp;
int N;
struct node {
node* left, *right;
int mx;
int mn;
void update() {
mn = min(left->mn ,right->mn);
mx = max(left->mx ,right->mx);
}
};
node* MAIN_NODE;
pair<int,int> query(node* root, int left, int right, int qLeft, int qRight) {
if(qLeft>qRight) swap(qLeft, qRight);
if (left > qRight || right < qLeft) return {-1,-1};
if (left >= qLeft && right <= qRight) return {root->mn,root->mx};
int mid = (left + right) / 2;
pair<int,int> q1=query(root->left, left, mid, qLeft, qRight),q2=query(root->right, mid + 1, right, qLeft, qRight);
if(q1.first==-1) return {q2.first,q2.second};
if(q2.first==-1) return {q1.first,q1.second};
return {min(q1.first,q2.first),max(q1.second,q2.second)};
}
void build(node* root, int left, int right) {
if (left == right) {
root->mn = indx[left];
root->mx = indx[left];
return;
}
int mid = (left + right) / 2;
root->left = new node{ NULL, NULL, 0, 0 };
root->right = new node{ NULL, NULL, 0, 0 };
build(root->left, left, mid);
build(root->right, mid+1, right);
root->update();
}
void destroy(node* root) {
if (root->left) destroy(root->left);
if (root->right) destroy(root->right);
delete root;
}
bool bsta(int s, int e, int L, int R){
s=mp[s];
e=mp[e];
int l=s, r=e;
if(l>r) swap(l,r);
while(l<r){
int mid=((l+r+1)/2);
int qH,qW;
if(s<e){
qH=query(MAIN_NODE, 0, N-1, s,mid-1).first;
qW=query(MAIN_NODE, 0, N-1, mid,e).second;
}else{
qH=query(MAIN_NODE, 0, N-1, s,mid+1).first;
qW=query(MAIN_NODE, 0, N-1, mid,e).second;
}
if(qH<L&&qW>R) return false;
else if(qH<L) {
if(s>e) l=mid+1;
else r=mid-1;
} else if(qW>R){
if(s>e) r=mid-1;
else l=mid+1;
}else return true;
}
int qH,qW;
if(s<e){
qH=query(MAIN_NODE, 0, N-1, s,l-1).first;
qW=query(MAIN_NODE, 0, N-1, l,e).second;
}else{
qH=query(MAIN_NODE, 0, N-1, s,l+1).first;
qW=query(MAIN_NODE, 0, N-1, l,e).second;
}
if(qH<L||qW>R) return false;
return true;
}
std::vector<int> check_validity(signed n, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> S, std::vector<signed> E, std::vector<signed> L, std::vector<signed> R) {
N=n;
int Q = S.size();
std::vector<int> A(Q);
indx.resize(N);
int leaf=0;
vector<vector<int>> adj(N);
for (int i = 0; i < n-1; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]);}
for (int i = 0; i < N; i++) if(adj[i].size()==1) { leaf=i; break; }
indx[0]=leaf;
indx[1]=adj[leaf][0];
mp[indx[0]]=0;
mp[indx[1]]=1;
for (int i = 2; i < N; i++)
{
if(adj[indx[i-1]][0]==indx[i-2]) indx[i]=adj[indx[i-1]][1];
else indx[i]=adj[indx[i-1]][0];
mp[indx[i]]=i;
}
MAIN_NODE=new node{NULL, NULL, 0, 0};
build(MAIN_NODE, 0, N-1);
for (int i = 0; i < Q; ++i) {
A[i] = bsta(S[i],E[i],L[i],R[i]);
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
717 ms |
44300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
