#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#else
#include"bits/stdc++.h"
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const int N = 2e5+5;
const int LN = 18;
int n, m, q;
V<int> adj[N];
V<int> ans;
int a[N];
struct Stable{
int mn[N][LN], mx[N][LN];
void build(){
rep(i,0,N) mn[i][0] = mx[i][0] = a[i];
rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<N; i++){
mn[i][lg] = min(mn[i][lg-1], mn[i+(1<<lg)][lg-1]);
mx[i][lg] = max(mx[i][lg-1], mx[i+(1<<lg)][lg-1]);
}
}
int qryMin(int l,int r){
int lg = __lg(r-l+1);
return min(mn[l][lg], mn[r-(1<<lg)+1][lg]);
}
int qryMax(int l,int r){
int lg = __lg(r-l+1);
return max(mx[l][lg], mx[r-(1<<lg)+1][lg]);
}
} stable;
int ord[N];
void dfs_ord(int x){
a[ord[x]] = x;
for(int y : adj[x]) if(ord[y]==-1){
ord[y] = ord[x]+1;
dfs_ord(y);
}
}
V<int> check_validity(int _n,V<int>_u, V<int>_v,
V<int>_s, V<int>_e,V<int>_l,V<int>_r){
n=_n; m=_u.size(); q=_s.size();
ans = V<int>(q);
rep(i,0,m){
adj[_u[i]].push_back(_v[i]);
adj[_v[i]].push_back(_u[i]);
}
rep(i,0,n) ord[i] = -1;
rep(i,0,n) if(adj[i].size()==1){
ord[i] = 0;
dfs_ord(i);
break;
}
assert(ord[0]!=-1);
stable.build();
// rep(i,0,n) cout << a[i] << " ";
// cout << nl;
rep(i,0,q){
int s = _s[i], e = _e[i];
int l = _l[i], r = _r[i];
int si = ord[s], ei = ord[e];
// dbg(si); dbg(ei);
if(si < ei){
int p = si, q = ei;
for(int J=1<<LN; J; J/=2){
if(p+J<=ei && stable.qryMin(si,p+J)>=l) p+=J;
if(q-J>=si && stable.qryMax(q-J,ei)<=r) q-=J;
}
// dbg(p); dbg(q);
ans[i] = q<=p;
}
if(ei < si){
int p = ei, q = si;
for(int J=1<<LN; J; J/=2){
if(p+J<=si && stable.qryMax(ei,p+J)<=r) p+=J;
if(q-J>=ei && stable.qryMin(q-J,si)>=l) q-=J;
}
ans[i] = q<=p;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
33108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
33108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
549 ms |
61492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
33108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
