#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int s, e, maxi;
Node *l, *r;
Node (int st, int en){
l = NULL;
r = NULL;
s = st;
e = en;
if(s!=e){
l = new Node(s,(s+e)/2);
r = new Node((s+e)/2+1,e);
}
maxi = 0;
}
int first (int bound){
if(s==e){
if(maxi>bound){
return s;
}
return 99999999;
}
if(l->maxi >bound){
return l->first(bound);
}
return r->first(bound);
}
int getmaxi(int st, int en){
if(st<=s && e<=en){
return maxi;
}
int ret = -1;
if(st<=(s+e)/2){
ret = max(ret,l->getmaxi(st,en));
}
if(en>(s+e)/2){
ret = max(ret,r->getmaxi(st,en));
}
}
void sett(int ind, int val){
if(s==e){
maxi = val;
}
else{
if(ind<=(s+e)/2){
l->sett(ind,val);
}
else{
r->sett(ind,val);
}
maxi = max(l->maxi,r->maxi);
}
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int need[n];
need[0] = 0;
//need[i] is the lock on the left side of room i
for(int i = 1; i<n; i++){
cin >> need[i];
need[i]--;
}
int last[n];
int left[n];
//how far left do you need to go to get a key that can open the lock to the left of this room
vector<int> keys[n];
for(int i = 0; i<n; i++){
int len;
cin >> len;
for(int j =0 ; j<len; j++){
int x;
cin >> x;
x--;
keys[i].push_back(x);
}
}
int right[n];
//how far left do you need to go to get a key that can open the lock to the right of this room
for(int i = 0; i<n; i++){
last[i] = -1;
}
for(int i = 0; i<n; i++){
left[i] = last[need[i]];
for(int j = 0; j<keys[i].size(); j++){
last[keys[i][j]] = i;
}
}
for(int i = 0; i<n; i++){
last[i] = n;
}
for(int i = n-1; i>=0; i--){
if(i==n-1){
right[i] = n;
}
else{
right[i] = last[need[i+1]];
}
for(int j = 0; j<keys[i].size(); j++){
last[keys[i][j]] = i;
}
}
vector<pair<int, int> > qbef[n];
//starting is before this
vector<pair<int, int> > qaft[n];
//starting is after this
int q;
cin >> q;
int ans[q];
for(int i = 0; i<q; i++){
ans[i] = -1;
int s, t;
cin >> s >> t;
s--;
t--;
if(s<t){
qbef[t].push_back(make_pair(s,i));
}
else{
qaft[t].push_back(make_pair(s,i));
}
}
Node *t = new Node(0,n-1);
for(int i = 0; i<n; i++){
t->sett(i,right[i]);
}
//going from left to right
bool inli[n];
for(int i = 0; i<n; i++){
inli[i] = false;
}
vector<int> possible;
possible.push_back(0);
inli[0] = true;
for(int i = 1; i<n; i++){
while(possible.size()>0){
int to = left[i];
if(to>=possible[possible.size()-1]){
break;
}
if(to<0){
inli[possible.size()-1] = false;
possible.pop_back();
continue;
}
int maxi = t->getmaxi(to,possible[possible.size()-1]-1);
if(maxi>=i){
inli[possible.size()-1] = false;
possible.pop_back();
}
else{
break;
}
}
possible.push_back(i);
inli[i] = true;
for(int j = 0; j<qbef[i].size(); j++){
ans[qbef[i][j].second] = inli[qbef[i][j].first];
}
}
for(int i = 0; i<possible.size(); i++){
inli[possible[i]] = false;
}
possible.clear();
//need[0] is 0, need[1] is need[n-1]
int tmp[n];
tmp[0] = 0;
for(int i = 1; i<n; i++){
tmp[i] = need[n-i];
}
for(int i = 0; i<n; i++){
need[i] = tmp[i];
}
for(int i = 0; i<n; i++){
last[i] = -1;
}
for(int i = 0; i<n; i++){
left[i] = last[need[i]];
for(int j = 0; j<keys[n-i-1].size(); j++){
last[keys[n-i-1][j]] = i;
}
}
for(int i = 0; i<n; i++){
last[i] = n;
}
for(int i = n-1; i>=0; i--){
if(i==n-1){
right[i] = n;
}
else{
right[i] = last[need[i+1]];
}
for(int j = 0; j<keys[n-i-1].size(); j++){
last[keys[n-1-i][j]] = i;
}
}
for(int i = 0; i<n; i++){
qbef[i].clear();
}
for(int i = 0; i<n; i++){
for(int j = 0; j<qaft[i].size(); j++){
qbef[n-i-1].push_back(make_pair(n-qaft[i][j].first-1,qaft[i][j].second));
}
}
for(int i = 0; i<n; i++){
t->sett(i,right[i]);
}
possible.push_back(0);
inli[0] = true;
for(int i = 1; i<n; i++){
while(possible.size()>0){
int to = left[i];
if(to>=possible[possible.size()-1]){
break;
}
if(to<0){
inli[possible.size()-1] = false;
possible.pop_back();
continue;
}
int maxi = t->getmaxi(to,possible[possible.size()-1]-1);
if(maxi>=i){
inli[possible.size()-1] = false;
possible.pop_back();
}
else{
break;
}
}
possible.push_back(i);
inli[i] = true;
for(int j = 0; j<qbef[i].size(); j++){
ans[qbef[i][j].second] = inli[qbef[i][j].first];
}
}
for(int i = 0; i<q; i++){
cout << (ans[i]?"YES":"NO") << endl;
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<keys[i].size(); j++){
~^~~~~~~~~~~~~~~
long_mansion.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<keys[i].size(); j++){
~^~~~~~~~~~~~~~~
long_mansion.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<qbef[i].size(); j++){
~^~~~~~~~~~~~~~~
long_mansion.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<possible.size(); i++){
~^~~~~~~~~~~~~~~~
long_mansion.cpp:189:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<keys[n-i-1].size(); j++){
~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:204:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<keys[n-i-1].size(); j++){
~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:212:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<qaft[i].size(); j++){
~^~~~~~~~~~~~~~~
long_mansion.cpp:243:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<qbef[i].size(); j++){
~^~~~~~~~~~~~~~~
long_mansion.cpp: In member function 'int Node::getmaxi(int, int)':
long_mansion.cpp:41:3: warning: control reaches end of non-void function [-Wreturn-type]
}
^
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:136:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
bool inli[n];
^~~~
long_mansion.cpp:136:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1308 ms |
43756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
