This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// rama_pang orz
// solution and codestyle adapted from his/her submission
#include<bits/stdc++.h>
using namespace std;
struct DisjointSet {
int n;
vector<int> f;
DisjointSet () = default;
DisjointSet (const int& _n): n(_n), f(n) { iota(begin(f), end(f), 0); }
int F(int u) { return u == f[u] ? u : f[u] = F(f[u]); }
bool M(int u, int v) {
u = F(u); v = F(v);
if (u != v) f[v] = u;
return u != v;
}
};
const int kN = 500005;
int N, Q, C[kN], B[kN];
vector<int> A[kN];
vector<int> key_pos[kN];
bool can_unlock(int l, int r, int c) {
return *lower_bound(begin(key_pos[c]), end(key_pos[c]), l) <= r;
}
pair<int, int> memo[kN];
bool in_stack[kN];
DisjointSet dsu(kN);
array<int, 3> solve(int u) {
if (in_stack[u]) return {u, u, u};
if (dsu.F(u) != u) return solve(dsu.F(u));
if (memo[u].first != 0) return {0, memo[u].first, memo[u].second};
in_stack[u] = true;
int lb = u, rb = u;
while (true) {
if (lb > 1 and can_unlock(lb, rb, C[lb - 1])) {
auto nxt = solve(lb - 1);
lb = min(lb, nxt[1]);
rb = max(rb, nxt[2]);
if (nxt[0] != 0 and dsu.M(nxt[0], u)) {
in_stack[u] = false;
return {nxt[0], lb, rb};
}
} else if (rb < N and can_unlock(lb, rb, C[rb])) {
auto nxt = solve(rb + 1);
lb = min(lb, nxt[1]);
rb = max(rb, nxt[2]);
if (nxt[0] != 0 and dsu.M(nxt[0], u)) {
in_stack[u] = false;
return {nxt[0], lb, rb};
}
} else break;
}
in_stack[u] = false;
memo[u] = {lb, rb};
return {0, lb, rb};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 1; i < N; ++i)
cin >> C[i];
for (int i = 1; i <= N; ++i) {
cin >> B[i];
A[i].resize(B[i]);
for (int& a: A[i]) {
cin >> a;
key_pos[a].emplace_back(i);
}
}
for (int i = 1; i <= N; ++i)
key_pos[i].emplace_back(N + 1);
cin >> Q;
for (int X, Y, i = 0; i < Q; ++i) {
cin >> X >> Y;
const auto ans = solve(X);
cout << (ans[1] <= Y and Y <= ans[2] ? "YES\n" : "NO\n");
}
return 0;
}
# | 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... |