# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
296308 | BThero | Long Mansion (JOI17_long_mansion) | C++17 | 1572 ms | 121636 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = (int)5e5 + 5;
vector<int> group[MAXN];
vector<int> keys[MAXN];
int betw[MAXN];
int A[MAXN], B[MAXN];
int L[MAXN], R[MAXN];
int n, q;
void calcB() {
B[0] = n + 1;
for (int i = 1; i <= n; ++i) {
group[i].clear();
B[i] = n + 1;
}
for (int i = 2; i <= n; ++i) {
group[betw[i - 1]].pb(i - 1);
for (int x : keys[i]) {
for (int y : group[x]) {
B[y] = i;
}
group[x].clear();
}
}
}
void calcA() {
A[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
group[i].clear();
A[i] = 0;
}
for (int i = n - 1; i > 0; --i) {
group[betw[i]].pb(i + 1);
for (int x : keys[i]) {
for (int y : group[x]) {
A[y] = i;
}
group[x].clear();
}
}
}
void calcR() {
for (int i = 1; i <= n; ++i) {
R[i] = n + 1;
}
for (int i = 0; i <= n + 1; ++i) {
group[i].clear();
}
for (int i = 1; i <= n; ++i) {
group[B[i - 1]].pb(i);
}
set<int> S, T;
for (int i = 1; i <= n + 1; ++i) {
S.insert(i);
T.insert(i);
}
for (int r = 1; r <= n; ++r) {
for (int x : group[r]) {
S.erase(x);
}
// A[r + 1] < l
int l = A[r + 1] + 1;
l = *S.lower_bound(l);
// B[l - 1] > r
auto it = T.lower_bound(l);
while (*it <= r) {
R[*it] = r;
it = T.erase(it);
}
}
}
void calcL() {
for (int i = 1; i <= n; ++i) {
L[i] = 0;
}
for (int i = 0; i <= n + 1; ++i) {
group[i].clear();
}
for (int i = 1; i <= n; ++i) {
group[A[i + 1]].pb(i);
}
set<int> S, T;
for (int i = 0; i <= n + 1; ++i) {
S.insert(i);
T.insert(i);
}
for (int l = n; l > 0; --l) {
for (int x : group[l]) {
S.erase(x);
}
// B[l - 1] > r
int r = B[l - 1] - 1;
r = *(--S.upper_bound(r));
// A[r + 1] < l
auto it = T.lower_bound(l);
while (*it <= r) {
L[*it] = l;
it = T.erase(it);
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d", &betw[i]);
}
for (int i = 1; i <= n; ++i) {
int sz;
scanf("%d", &sz);
keys[i].resize(sz);
for (int j = 0; j < sz; ++j) {
scanf("%d", &keys[i][j]);
}
}
calcB();
calcA();
calcR();
calcL();
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
int a, b;
scanf("%d %d", &a, &b);
// a -> b
bool ans = 1;
if (a < b) {
if (R[a] < b) {
ans = 0;
}
}
else {
if (L[a] > b) {
ans = 0;
}
}
if (ans) {
printf("YES\n");
}
else {
printf("NO\n");
}
}
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |