Submission #538033

#TimeUsernameProblemLanguageResultExecution timeMemory
538033fhvirusLong Mansion (JOI17_long_mansion)C++17
100 / 100
366 ms76664 KiB
// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...