QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603744#8720. BFS 序 0reaepitaRE 0ms0kbC++141.9kb2024-10-01 18:45:392024-10-01 18:45:40

Judging History

This is the latest submission verdict.

  • [2024-10-01 18:45:40]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-10-01 18:45:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
vector<int> G[maxn];
vector<int> G2[maxn];
int fa[maxn][20], dep[maxn];
void dfs(int u)
{
	for (int i = 1; i <= 19; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		dep[v] = dep[u] + 1;
		dfs(v);
	}
}
int lca(int u, int v)
{
	if (dep[u] < dep[v])
		swap(u, v);
	for (int i = 19; i >= 0; i--)
		if (dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if (u == v)
		return u;
	for (int i = 19; i >= 0; i--)
		if (fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
int in[maxn];
bool topsort(vector<int> V)
{
	int t = 0;
	queue<int> q;
	for (auto x : V)
		if (!in[x])
			q.push(x);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		t++;
		for (int i = 0; i < G2[u].size(); i++)
		{
			int v = G2[u][i];
			in[v]--;
			if (!in[v])
				q.push(v);
		}
	}
	for (auto x : V)
		in[x] = 0, G2[x].clear();
	return t == V.size();
}
int n, q;
int main()
{
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		fa[i][0] = x;
		G[x].push_back(i);
	}
	dfs(1);
	scanf("%d", &q);
	while (q--)
	{
		vector<int> v;
		int k;
		scanf("%d", &k);
		int a, b, flag = 0;
		int lst, cur;
		while (k--)
		{
			scanf("%d", &cur);
			b = lst, a = cur;
			if (dep[b] > dep[a])
				flag = 1;
			if (b && dep[a] == dep[b])
			{

				int c = lca(a, b);
				for (int i = 19; i >= 0; i--)
					if (dep[fa[a][i]] > dep[c])
						a = fa[a][i];
				for (int i = 19; i >= 0; i--)
					if (dep[fa[b][i]] > dep[c])
						b = fa[b][i];
				G2[b].push_back(a);
				in[a]++;
				v.push_back(a);
				v.push_back(b);
			}
			lst = cur;
		}
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		if (topsort(v) && (!flag))
			puts("YES");
		else
			puts("NO");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6

output:


result: