// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> c(n);
for (int i = 0; i < n - 1; i++) {
cin >> c[i];
--c[i];
}
vector<int> b(n);
vector<vector<int>> a(n);
for (int i = 0; i < n; i++) {
cin >> b[i];
a[i].resize(b[i]);
for (int j = 0; j < b[i]; j++) {
cin >> a[i][j];
--a[i][j];
}
}
vector<int> par(n);
iota(par.begin(), par.end(), 0);
function<int(int)> Get = [&](int x) {
return par[x] == x ? x : par[x] = Get(par[x]);
};
vector<int> L(n), R(n), myL(n), myR(n);
vector<vector<int>> alive(n);
vector<set<int>> keys(n);
set<int> none, canL, canR, canLR;
auto CanL = [&](int i) {
i = Get(i);
return (L[i] > 0 && keys[i].find(c[L[i] - 1]) != keys[i].end());
};
auto CanR = [&](int i) {
i = Get(i);
return (R[i] + 1 < n && keys[i].find(c[R[i]]) != keys[i].end());
};
for (int i = 0; i < n; i++) {
L[i] = R[i] = i;
alive[i].push_back(i);
for (int j = 0; j < b[i]; j++) {
keys[i].insert(a[i][j]);
}
if (CanL(i) && CanR(i)) {
canLR.insert(i);
} else if (CanL(i)) {
canL.insert(i);
} else if (CanR(i)) {
canR.insert(i);
} else {
none.insert(i);
}
}
auto Merge = [&](int x, int y) {
if (x != Get(x)) {
while (true) {
}
}
if (y != Get(y)) {
while (true) {
}
}
x = Get(x);
y = Get(y);
if (x == y) {
return;
}
if (CanL(x) && CanR(x)) {
assert(canLR.find(x) != canLR.end());
canLR.erase(canLR.find(x));
} else if (CanL(x)) {
assert(canL.find(x) != canL.end());
canL.erase(canL.find(x));
} else if (CanR(x)) {
assert(canR.find(x) != canR.end());
canR.erase(canR.find(x));
} else {
assert(none.find(x) != none.end());
none.erase(none.find(x));
}
if (CanL(y) && CanR(y)) {
assert(canLR.find(y) != canLR.end());
canLR.erase(canLR.find(y));
} else if (CanL(y)) {
assert(canL.find(y) != canL.end());
canL.erase(canL.find(y));
} else if (CanR(y)) {
assert(canR.find(y) != canR.end());
canR.erase(canR.find(y));
} else {
assert(none.find(y) != none.end());
none.erase(none.find(y));
}
for (int i : keys[y]) {
keys[x].insert(i);
}
for (int i : alive[y]) {
alive[x].push_back(i);
}
alive[y].clear();
L[x] = min(L[x], L[y]);
R[x] = max(R[x], R[y]);
par[y] = x;
if (CanL(x) && CanR(x)) {
canLR.insert(x);
} else if (CanL(x)) {
canL.insert(x);
} else if (CanR(x)) {
canR.insert(x);
} else {
none.insert(x);
}
};
while (true) {
if (!none.empty()) {
auto it = none.begin();
int c = *it;
none.erase(it);
for (int i : alive[c]) {
myL[i] = L[c];
myR[i] = R[c];
}
alive[c].clear();
continue;
}
if (!canL.empty()) {
auto it = canL.begin();
int c = *it;
Merge(Get(L[c] - 1), c);
continue;
}
if (!canR.empty()) {
auto it = prev(canR.end());
int c = *it;
Merge(c, Get(R[c] + 1));
continue;
}
if (!canLR.empty()) {
auto it = canLR.begin();
int c = *it;
Merge(Get(L[c] - 1), c);
continue;
}
break;
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
cout << (myL[x] <= y && y <= myR[x] ? "YES" : "NO") << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
178 ms |
89936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
