#include<bits/stdc++.h>
#include "werewolf.h"
#define fi first
#define se second
using namespace std;
const int NN=2e5;
struct Que
{
int l,r,s,e,id;
};
struct Node
{
bool vis=false;
int l,r;
int id;
vector<Node*> e;
Node* par;
Node(int _id) : id(_id)
{
par=nullptr;
}
Node* f()
{
if(par==nullptr)
return this;
par=(par->f());
return par;
}
void add_e(Node* x)
{
if(x==this)
return;
e.push_back(x);
x->par=this;
return;
}
int dfs(int nr)
{
if(vis)
return nr;
vis=true;
if(l==-1)
{
l=r=++nr;
//cerr<<id<<" "<<l<<"\n";
return nr;
}
l=nr+1;
for(auto v:e)
nr=v->dfs(nr);
r=nr;
return nr;
}
};
vector<int> e[NN+10];
Que qq[NN+10];
Node* nd[2*NN+10];
Node* tmpq[NN+10];
set<int> st[NN+10];
int fau[NN+10];
pair<int,int> in[NN+10];
vector<int> ans;
bool comp_l(Que a,Que b)
{
return a.l<b.l;
}
bool comp_r(Que a,Que b)
{
return a.r<b.r;
}
int f(int x)
{
if(fau[x]!=x)
fau[x]=f(fau[x]);
return fau[x];
}
void u(int x,int y)
{
x=f(x);
y=f(y);
if(x==y)
return;
if(st[x].size()<st[y].size())
swap(x,y);
for(auto v:st[y])
st[x].insert(v);
{set<int> ().swap(st[y]);}
fau[y]=x;
return;
}
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 n=N;
ans.resize(q);
for(size_t i=0;i<X.size();i++)
{
e[X[i]].push_back(Y[i]);
e[Y[i]].push_back(X[i]);
}
for(int i=0;i<q;i++)
qq[i]={L[i],R[i],S[i],E[i],i};
sort(qq,qq+q,comp_l);
for(int i=0;i<n;i++)
nd[i]=new Node(i);
for(int i=n-1,j=q-1;i>=0;i--)
{
nd[n+(n-1-i)]=new Node(n+(n-1-i));
auto x=nd[n+(n-1-i)];
x->add_e(nd[i]->f());
for(auto v:e[i])
{
if(v>=i)
x->add_e(nd[v]->f());
}
while(j>=0 && qq[j].l==i)
{
tmpq[j]=(nd[qq[j].s]->f());
j--;
}
}
for(int i=0;i<n;i++)
(nd[i]->l)=(nd[i]->r)=-1;
for(int i=n;i<2*n;i++)
(nd[i]->l)=(nd[i]->r)=0;
for(int i=0,lst=-1;i<n;i++)
lst=(nd[i]->f())->dfs(lst);
for(int i=0;i<q;i++)
{
in[qq[i].id]={tmpq[i]->l,tmpq[i]->r};
//cerr<<qq[i].id<<" "<<in[qq[i].id].fi<<" "<<in[qq[i].id].se<<"\n";
}
sort(qq,qq+q,comp_r);
for(int i=0;i<n;i++)
{
fau[i]=i;
st[i]={nd[i]->l};
}
for(int i=0,j=0;i<n;i++)
{
for(auto v:e[i])
{
if(v<i)
u(v,i);
}
while(j<q && qq[j].r==i)
{
int x=f(qq[j].r);
auto it=st[x].lower_bound(in[qq[j].id].fi);
ans[qq[j].id]=(it!=st[x].end() && *it<=in[qq[j].id].se);
j++;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
949 ms |
90976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
