#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(n+1);
}
void update(int x,int y){
for(;x<=n;x+=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
int ans=0;
for(;x>0;x-=(x&-x)){
ans+=bt[x];
}
return ans;
}
int sum(int l,int r){
return query(r)-query(l-1);
}
};
struct T1{
struct no{
vector<int> ch;
int in,out;
};
vector<no> v;
BIT bt;
int cnt=0;
void init(int x){
v.resize(x);
bt.init(x+1);
}
void add(int x,int y){
v[x].ch.push_back(y);
v[y].ch.push_back(x);
}
void dfs(int r,int f){
cnt++;
v[r].in=cnt;
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
}
}
v[r].out=cnt;
}
vector<int> s;
void ap(int r){
s.push_back(r);
bt.update(v[r].in,1);
}
int query(int r){
return bt.sum(v[r].in,v[r].out);
}
void undo(){
while(s.size()){
bt.update(v[s.back()].in,-1);
s.pop_back();
}
}
}t1;
vector<int> ans;
struct T2{
struct no{
vector<int> ch;
int sz=1;
int vis=0;
int mx=-1;
vector<pair<int,int> > qu;
};
vector<no> v;
int cnt=0;
void init(int x){
v.resize(x);
}
void add(int x,int y){
v[x].ch.push_back(y);
v[y].ch.push_back(x);
}
void aq(int r,pair<int,int> a){
v[r].qu.push_back(a);
}
void cal(int r,int f,int t){
if(!v[r].vis){
for(auto h:v[r].ch){
if(h!=f && h!=v[r].mx){
cal(h,r,1);
}
}
}
if(v[r].mx>=0){
cal(v[r].mx,r,0);
}
t1.ap(r);
for(auto h:v[r].ch){
if(h!=f && h!=v[r].mx){
cal(h,r,0);
}
}
if(!v[r].vis){
for(auto h:v[r].qu){
ans[h.fs]=t1.query(h.sc)>0;
}
v[r].vis=1;
}
if(t){
t1.undo();
}
}
void dfs(int r,int f){
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
v[r].sz+=v[h].sz;
if(v[r].mx==-1 || v[h].sz>v[v[r].mx].sz){
v[r].mx=h;
}
}
}
}
}t2;
struct DSU{
vector<int> bo;
void init(int x){
bo.resize(x);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
pair<int,int> merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return {-1,-1};
}
bo[y]=x;
return {x,y};
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y,
vector<int> s, vector<int> e,
vector<int> l, vector<int> r) {
int q=s.size();
int m=x.size();
vector<vector<int> > ls(n),re(n);
for(int i=0;i<q;i++){
ls[l[i]].push_back(i);
}
for(int i=0;i<q;i++){
re[r[i]].push_back(i);
}
ans.resize(q);
vector<vector<int> > f(n);
for(int i=0;i<m;i++){
f[x[i]].push_back(y[i]);
f[y[i]].push_back(x[i]);
}
t1.init(n);
DSU d1;
d1.init(n);
for(int i=0;i<n;i++){
for(auto z:f[i]){
if(z<i){
auto a=d1.merge(i,z);
if(a.fs>=0){
t1.add(a.fs,a.sc);
}
for(auto h:re[i]){
e[h]=d1.find(e[h]);
}
}
}
}
t1.dfs(n-1,n-1);
t2.init(n);
DSU d2;
d2.init(n);
for(int i=n-1;i>=0;i--){
for(auto z:f[i]){
if(z>i){
auto a=d2.merge(i,z);
if(a.fs>=0){
t2.add(a.fs,a.sc);
}
for(auto h:ls[i]){
s[h]=d2.find(s[h]);
t2.aq(s[h],{h,e[h]});
}
}
}
}
t2.dfs(0,0);
t2.cal(0,0,0);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
623 ms |
85180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
