Submission #705811

#TimeUsernameProblemLanguageResultExecution timeMemory
705811dooompyLong Mansion (JOI17_long_mansion)C++17
100 / 100
380 ms69832 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; int col[500005]; vector<int> keys[500005]; int seen[500005]; int leftt[500005], rightt[500005], par[500005]; int find(int node) { if (par[node] == node) return node; return (par[node] = find(par[node])); } void Union(int a, int b) { a = find(a); b = find(b); if (a == b) return; par[a] = b; } void dfs(int node) { seen[node] = 1; par[node] = node; leftt[node] = rightt[node] = node; while (1) { // try to extend int curleft = leftt[find(node)], curright = rightt[find(node)]; if (lower_bound(keys[col[curleft - 1]].begin(), keys[col[curleft - 1]].end(), curleft) != upper_bound(keys[col[curleft - 1]].begin(), keys[col[curleft - 1]].end(), curright)) { // can extend to left leftt[find(node)] = leftt[find(curleft - 1)]; if (seen[curleft - 1] == 1 && find(curleft - 1) != find(node)) { Union(node, curleft - 1); rightt[find(node)] = rightt[node]; } } if (lower_bound(keys[col[curright]].begin(), keys[col[curright]].end(), curleft) != upper_bound(keys[col[curright]].begin(), keys[col[curright]].end(), curright)) { if (seen[curright + 1] == 0) dfs(curright + 1); rightt[find(node)] = rightt[find(curright + 1)]; } if (curleft == leftt[find(node)] && curright == rightt[find(node)]) break; } seen[node] = 2; } int ansl[500005], ansr[500005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n; cin >> n; for (int i = 1; i < n; i++) cin >> col[i]; for (int i = 1; i <= n; i++) { int x; cin >> x; for (int j = 0; j < x; j++) { int t; cin >> t; keys[t].push_back(i); } } for (int i = 1; i <= n; i++) { if (!seen[i]) dfs(i); } for (int i = 1; i <= n; i++) { ansl[i] = leftt[find(i)]; ansr[i] = rightt[find(i)]; } int q ;cin >> q; while (q--) { int x, y; cin >> x >> y; if (y > ansr[x] || y < ansl[x]) { cout << "NO\n"; } else cout << "YES\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...