#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
int n;
int segtree[nax*4][2];
int tab[nax];
void build(int pos,int l,int r){
if(l==r){
segtree[pos][0]=segtree[pos][1]=tab[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
return;
}
int query0(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return 1e9;
if(l>=left&&r<=right) return segtree[pos][0];
int mid=(r+l)/2;
return min(query0(pos*2+1,l,mid,left,right),query0(pos*2+2,mid+1,r,left,right));
}
int query1(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return -1e9;
if(l>=left&&r<=right) return segtree[pos][1];
int mid=(r+l)/2;
return max(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int bs_min_left(int x,int cur){
int l=-1;
int r=x;
while(r-l>1){
int mid=(r+l)/2;
if (query0(0,0,n-1,mid,x)>=cur)
r=mid;
else l=mid;
}
return r;
}
int bs_min_right(int x,int cur){
int l=x;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if (query0(0,0,n-1,x,mid)>=cur)
l=mid;
else r=mid;
}
return l;
}
int bs_max_left(int x,int cur){
int l=-1;
int r=x;
while(r-l>1){
int mid=(r+l)/2;
if (query1(0,0,n-1,mid,x)<=cur)
r=mid;
else l=mid;
}
return r;
}
int bs_max_right(int x,int cur){
int l=x;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if (query1(0,0,n-1,x,mid)<=cur)
l=mid;
else r=mid;
}
return l;
}
set<int> mergesort[nax*4];
void build_mergesort(int pos,int l,int r){
if(l==r){
mergesort[pos].insert(tab[l]);
return;
}
int mid=(r+l)/2;
build_mergesort(pos*2+1,l,mid);
build_mergesort(pos*2+2,mid+1,r);
for(auto u:mergesort[pos*2+1]) mergesort[pos].insert(u);
for(auto u:mergesort[pos*2+2]) mergesort[pos].insert(u);
return;
}
bool query(int pos,int l,int r,int left,int right,pair<int,int> cur){
if(l>r||l>right||r<left) return 0;
if(l>=left&&r<=right){
return *mergesort[pos].lower_bound(cur.fi)<=cur.se;
}
int mid=(r+l)/2;
return query(pos*2+1,l,mid,left,right,cur)|query(pos*2+2,mid+1,r,left,right,cur);
}
int t=0;
int conv[nax];
void dfs(int x,int p){
conv[x]=t;
tab[t++]=x;
for(auto u:adj[x]){
if(u==p) continue;
dfs(u,x);
}
return;
}
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) {
n=N;
int q=R.size();
int v[n];
memset(v,0,sizeof v);
for (int i = 0; i < n-1; ++i)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
v[X[i]]++;
v[Y[i]]++;
}
int lst;
for (int i = 0; i < n; ++i)
{
if(v[i]==1){
lst=i;
}
}
dfs(lst,-1);
build(0,0,n-1);
build_mergesort(0,0,n-1);
vector<int> ans;
for (int i = 0; i < q; ++i)
{
pair<int,int> cur={L[i],R[i]};
S[i]=conv[S[i]];
E[i]=conv[E[i]];
bool test=(E[i]>=S[i]);
pair<int,int> cnt;
if(test){
int right=bs_min_right(S[i],cur.fi);
int left=bs_max_left(E[i],cur.se);
cnt={right,left};
}else{
int right=bs_min_left(S[i],cur.fi);
int left=bs_max_right(E[i],cur.se);
cnt={left,right};
}
if(cnt.fi<cnt.se){
ans.pb(0);
continue;
}
ans.pb((query(0,0,n-1,cnt.se,cnt.fi,cur)) ? 1 : 0);
}
return ans;
}
/*namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
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:135:8: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
135 | dfs(lst,-1);
| ~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
237320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
237320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1658 ms |
259044 KB |
Output is correct |
| 2 |
Correct |
2111 ms |
259312 KB |
Output is correct |
| 3 |
Correct |
2001 ms |
259276 KB |
Output is correct |
| 4 |
Correct |
2012 ms |
259292 KB |
Output is correct |
| 5 |
Correct |
2009 ms |
259424 KB |
Output is correct |
| 6 |
Correct |
1920 ms |
259388 KB |
Output is correct |
| 7 |
Correct |
1719 ms |
259384 KB |
Output is correct |
| 8 |
Correct |
1999 ms |
259532 KB |
Output is correct |
| 9 |
Correct |
1333 ms |
259376 KB |
Output is correct |
| 10 |
Correct |
1501 ms |
259292 KB |
Output is correct |
| 11 |
Correct |
1561 ms |
259232 KB |
Output is correct |
| 12 |
Correct |
1536 ms |
259328 KB |
Output is correct |
| 13 |
Correct |
2015 ms |
259292 KB |
Output is correct |
| 14 |
Correct |
2043 ms |
259216 KB |
Output is correct |
| 15 |
Correct |
1975 ms |
259292 KB |
Output is correct |
| 16 |
Correct |
1906 ms |
259300 KB |
Output is correct |
| 17 |
Correct |
1726 ms |
259276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
237320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
