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...