// Code by Parsa Eslami
#include <bits/stdc++.h>
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
using namespace std;
const int N=5e5+4;
vector<int> vc;
int X[N];
int n;
int L[N],R[N];
int l[N],r[N];
int pr[N],nxt[N];
int dsu[N];
int to[N];
int parent(int v){
if(dsu[v]<0) return v;
return (dsu[v]=parent(dsu[v]));
}
void join(int a,int b){
int u=a;
int v=b;
u=parent(u); v=parent(v);
//if(u==v) return;
if(dsu[u]<dsu[v]) swap(u,v);
dsu[v]+=dsu[u]; dsu[u]=v;
to[v]=b;
pr[b]=pr[a];
}
void dol(){
vector<int> vc0;
for(int i:vc){
int X=l[i];
while(1){
int Y=to[parent(l[i])];
int z=pr[Y];
if(z==0) break;
if(R[z]&&R[z]<=to[parent(r[i])]){
l[i]=l[z];
}else break;
}
if(l[i]!=X) vc0.pb(i);
}
vc=vc0;
}
void dor(){
vector<int> vc0;
FORR(j,SZ(vc)-1,0){
int i=vc[j];
int X=r[i];
while(1){
int Y=to[parent(r[i])];
int z=nxt[Y];
if(z==n+1) break;
if(L[z]&&L[z]>=to[parent(l[i])]){
r[i]=r[z];
}else break;
}
if(r[i]!=X) vc0.pb(i);
}
vc=vc0;
reverse(all(vc));
}
void Main(){
cin>>n;
FOR(i,1,n) dsu[i]=-1,to[i]=i;
FOR(i,1,n) nxt[i]=i+1,pr[i]=i-1;
int C[n+1]={};
FOR(i,1,n-1) cin>>C[i];
vector<int> B[N];
FOR(i,1,n){
int sz; cin>>sz;
FOR(j,1,sz){
int x0; cin>>x0;
B[i].pb(x0);
}
}
FOR(i,1,n){
if(i!=1&&X[C[i-1]]){
L[i]=X[C[i-1]];
}
FOR(j,0,SZ(B[i])-1){
X[B[i][j]]=i;
}
}
FOR(i,1,n){
FOR(j,0,SZ(B[i])-1){
X[B[i][j]]=0;
}
}
FORR(i,n,1){
if(i!=n&&X[C[i]]){
R[i]=X[C[i]];
}
FOR(j,0,SZ(B[i])-1){
X[B[i][j]]=i;
}
}
FOR(i,1,n) l[i]=r[i]=i;
FOR(i,1,n) vc.pb(i); dor();
vc.clear();
FOR(i,1,n) vc.pb(i); dol();
int sz=n;
while(!vc.empty()){
bool is[N]={};
for(int u0:vc) is[u0]=1;
FOR(i,0,SZ(vc)-2){
if(to[parent(r[vc[i]])]>=vc[i+1]&&to[parent(l[vc[i+1]])]<=vc[i]){
is[vc[i]]=0;;
join(vc[i],vc[i+1]);
}
i++;
}
vc.clear(); FOR(i,1,n) if(is[i]) vc.pb(i);
if(sz+1<2*SZ(vc)){
exit(0);
}
sz=SZ(vc);
dor();
if(vc.empty()) break;
dol();
}
int q; cin>>q;
while(q--){
int u,v; cin>>u>>v;
bool ans;
if(u<v){
ans=(r[to[parent(u)]]>=v);
}else ans=(v>=l[to[parent(u)]]);
cout<<(ans?"YES\n":"NO\n");
}
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int T=1;
while(T--) Main();
return 0;
}
Compilation message
long_mansion.cpp: In function 'void Main()':
long_mansion.cpp:6:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
6 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
| ^~~
long_mansion.cpp:114:3: note: in expansion of macro 'FOR'
114 | FOR(i,1,n) vc.pb(i); dor();
| ^~~
long_mansion.cpp:114:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
114 | FOR(i,1,n) vc.pb(i); dor();
| ^~~
long_mansion.cpp:6:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
6 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
| ^~~
long_mansion.cpp:116:3: note: in expansion of macro 'FOR'
116 | FOR(i,1,n) vc.pb(i); dol();
| ^~~
long_mansion.cpp:116:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
116 | FOR(i,1,n) vc.pb(i); dol();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
10 ms |
12980 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
12756 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
10 ms |
12980 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
12756 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
22164 KB |
Output is correct |
| 2 |
Correct |
191 ms |
22032 KB |
Output is correct |
| 3 |
Correct |
164 ms |
22084 KB |
Output is correct |
| 4 |
Correct |
162 ms |
22164 KB |
Output is correct |
| 5 |
Correct |
169 ms |
22216 KB |
Output is correct |
| 6 |
Incorrect |
48 ms |
20512 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
10 ms |
12980 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
12756 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
