이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "werewolf.h"
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>
using namespace std;
const int MAXN = 2*100*1000 +1;
const int INF = 2*MAXN;
vi g[MAXN];
int n;
struct SegmentTree{
int st[4*MAXN];
void build(int node,int ss,int se,int* arr){
if(ss == se){
st[node] = arr[ss];
return;
}
int mid = (ss+se)/2;
build(node*2+1,ss,mid,arr);
build(node*2+2,mid+1,se,arr);
st[node] = min(st[node*2+1],st[node*2+2]);
}
int getLastValue(int node,int ss,int se,int bound,int val){
if(ss > bound)return -1;
if(st[node] >= val)return -1;
int mid = (ss+se)/2;
if(ss == se)return ss;
int vv = getLastValue(node*2+2,mid+1,se,bound,val);
if(vv == -1)return getLastValue(node*2+1,ss,mid,bound,val);
return vv;
}
};
SegmentTree human_normal,human_reverse,wolf_normal,wolf_reverse;
int place[MAXN];
int rplace[MAXN];
int T = 0;
void dfs(int node,int p = -1){
place[node] = T;
rplace[T] = node;
T++;
for(auto e : g[node]){
if(e != p)dfs(e,node);
}
}
bool solve(int n,int l,int r,int s,int e){
s = place[s];
e = place[e];
ii p1;
ii p2;
p1.ff = human_normal.getLastValue(0,0,n-1,s,l) + 1;
p1.ss = n - human_reverse.getLastValue(0,0,n-1,n-s-1,l) - 1 -1;
p2.ff = wolf_normal.getLastValue(0,0,n-1,e,-r) + 1;
p2.ss =n - wolf_reverse.getLastValue(0,0,n-1,n-e-1,-r) - 1 -1;
if(p1.ff == p2.ff)return true;
if(p1.ff > p2.ff)swap(p1,p2);
return p1.ss >= p2.ff;
}
vi check_validity(int n,vi x,vi y,vi s,vi e,vi l,vi r){
FOR(i,(int)x.size()){
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
::n = n;
int q = s.size();
vi ret;FOR(i,q)ret.pb(0);
// preprocess stuff
int root = 0;
FOR(i,n)if(g[i].size() == 1)root = i;
dfs(root);
int arr[n];
FOR(i,n)arr[i] = rplace[i];
human_normal.build(0,0,n-1,arr);
FOR(i,n)arr[i] = rplace[n-i-1];
human_reverse.build(0,0,n-1,arr);
FOR(i,n)arr[i] = -rplace[i];
wolf_normal.build(0,0,n-1,arr);
FOR(i,n)arr[i] = -rplace[n-i-1];
wolf_reverse.build(0,0,n-1,arr);
//////////////////////////////////
FOR(i,q){
ret[i] = solve(n,l[i],r[i],s[i],e[i]);
}
return ret;
}
int ma1in(){
ios_base::sync_with_stdio(0);
cin.tie(0);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |