#include "bits/stdc++.h"
using namespace std;
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1;
int r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) {
int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() {
f[0] = 1;
for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}
vector<int> adj[MAXN];
int l[MAXN], r[MAXN], c[MAXN];
vector<int> List[MAXN];
unordered_map<int, int> contains[MAXN];
bool vis[MAXN];
int n;
stack<int> topo;
void dfs(int node) {
vis[node] = 1;
for(int x: adj[node]) {
if(!vis[x]) {
dfs(x);
}
}
topo.push(node);
}
vector<int> adj2[MAXN], adj3[MAXN];
vector<vector<int> > compo;
vector<int> single;
void dfs2(int node) {
vis[node] = 1;
for(int x: adj2[node]) {
if(!vis[x]) dfs2(x);
}
single.push_back(node);
}
int dsu[MAXN];
int set_of(int u) {
if(dsu[u] == u) return u;
return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
dsu[set_of(u)] = set_of(v);
}
void dfs3(int node) {
vis[node] = 1;
topo.push(node); // reverse topo order
for(int x: adj3[node]) {
if(!vis[x]) {
dfs3(x);
}
}
}
vector<int> savior[MAXN]; // savior[i]: which nodes contain key i
void solve(int tc) {
cin >> n;
for(int i=1; i<=n; i++) {
dsu[i] = i;
}
for(int i=1; i<n; i++) {
cin >> c[i];
}
for(int i=1; i<=n; i++) {
int x;
cin >> x;
for(int j=0; j<x; j++) {
int y;
cin >> y;
List[i].push_back(y);
savior[y].push_back(i);
contains[i][y] = 1;
}
}
for(int i=1; i<n; i++) {
if(contains[i][c[i]]) adj[i].push_back(i + 1);
if(contains[i+1][c[i]]) adj[i + 1].push_back(i);
}
for(int i=1; i<=n; i++) {
if(!vis[i]) {
dfs(i);
}
}
for(int i=1; i<=n; i++) {
vis[i] = 0;
for(int j=0; j<adj[i].size(); j++) {
adj2[adj[i][j]].push_back(i);
}
}
while(topo.size()) {
int t = topo.top(); topo.pop();
if(!vis[t]) {
single.clear();
dfs2(t);
compo.push_back(single);
}
}
for(vector<int> v: compo) {
for(int i=1; i<v.size(); i++) {
if(set_of(v[i]) != set_of(v[i-1])) union_(v[i], v[i-1]);
}
}
map<pair<int, int>, int> exists;
for(int i=1; i<=n; i++) {
for(int x: adj[i]) {
int si = set_of(i), sx = set_of(x);
if(si != sx && !exists[{si, sx}]) {
exists[{si, sx}] = exists[{sx, si}] = 1;
adj3[si].push_back(sx);
}
}
}
for(int i=1; i<=n; i++) vis[i] = 0;
for(int i=1; i<=n; i++) {
if(set_of(i) == i && !vis[i]) {
dfs3(i);
}
}
int mi[n+1], ma[n+1];
for(int i=1; i<=n; i++) mi[i] = 1e9, ma[i] = 0;
for(int i=1; i<=n; i++) mi[set_of(i)] = min(mi[set_of(i)], i), ma[set_of(i)] = max(ma[set_of(i)], i);
for(int i=1; i<=n; i++) mi[i] = mi[set_of(i)], ma[i] = ma[set_of(i)];
for(int i=1; i<=n; i++) l[i] = mi[set_of(i)], r[i] = ma[set_of(i)];
while(topo.size()) {
int t = topo.top(); topo.pop();
for(int x: adj3[t]) {
l[t] = min(l[t], l[x]);
r[t] = max(r[t], r[x]);
}
if(adj3[t].empty()) continue;
while(1) {
bool can = 0;
if(mi[l[t]] > 1) {
int key_id = c[l[t] - 1];
if(savior[key_id].size()) {
if(savior[key_id][savior[key_id].size() - 1] >= l[t]) {
int lwb = *lower_bound(savior[key_id].begin(), savior[key_id].end(), l[t]);
if(lwb <= r[t]) {
l[t] = mi[l[t] - 1];
can = 1;
}
}
}
}
if(ma[r[t]] < n) {
int key_id = c[r[t]];
if(savior[key_id].size()) {
if(savior[key_id][savior[key_id].size() - 1] >= l[t]) {
int lwb = *lower_bound(savior[key_id].begin(), savior[key_id].end(), l[t]);
if(lwb <= r[t]) {
r[t] = ma[r[t] + 1];
can = 1;
}
}
}
}
if(!can) break;
}
}
for(int i=1; i<=n; i++) {
l[i] = l[set_of(i)], r[i] = r[set_of(i)];
}
int q;
cin >> q;
while(q--) {
int x, y; cin >> x >> y;
cout << (l[x] <= y && y <= r[x] ? "YES\n" : "NO\n");
}
}
int32_t main(){
precomp();
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
long_mansion.cpp: In function 'void solve(long long int)':
long_mansion.cpp:115:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int j=0; j<adj[i].size(); j++) {
| ~^~~~~~~~~~~~~~
long_mansion.cpp:128:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=1; i<v.size(); i++) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
91268 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
91732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
91268 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
91732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
148088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
91268 KB |
Output is correct |
| 2 |
Incorrect |
129 ms |
91732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
