Submission #1361465

#TimeUsernameProblemLanguageResultExecution timeMemory
1361465Jawad_Akbar_JJLong Mansion (JOI17_long_mansion)C++20
100 / 100
121 ms41368 KiB
#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<19;
vector<int> A[N];
int L[N], R[N], c[N], ind[N], nxt[N], lst[N];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); 
	int n, q;
	cin>>n;

	for (int i=2;i<=n;i++)
		cin>>c[i];

	for (int i=1, s;i<=n;i++){
		cin>>s;

		A[i].resize(s);
		for (int &j : A[i])
			cin>>j;
	}

	for (int i=1;i<n;i++){
		for (int j : A[i])
			ind[j] = i;
		
		lst[i+1] = ind[c[i+1]];
	}

	for (int i=1;i<=n;i++)
		ind[i] = n + 1, L[i] = R[i] = i;

	for (int i=n;i - 1;i--){
		for (int j : A[i])
			ind[j] = i;
		nxt[i] = ind[c[i]];
	}

	for (int i=1;i<=n;){
		if (L[i] > 1 and nxt[L[i]] <= R[i])
			R[i] = max(R[i], R[L[i]-1]), L[i] = L[L[i]-1];
		else if (R[i] < n and lst[R[i]+1] >= L[i])
			R[i]++;
		else
			i++;
	}

	cin>>q;
	for (int i=1, x, y;i<=q;i++){
		cin>>x>>y;
		if (L[x] <= y and y <= R[x])
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...