QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#422110#8720. BFS 序 0MaxDYFWA 0ms3808kbC++232.4kb2024-05-26 19:38:162024-05-26 19:38:16

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 19:38:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3808kb
  • [2024-05-26 19:38:16]
  • 提交

answer

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int f[N][25];
vector<int> G[N];
int dep[N];
void dfs(int x)
{
	dep[1] = 1;
	for (int i = 1; i < 25; i++)
		f[x][i] = f[f[x][i - 1]][i - 1];
	for (auto y : G[x])
	{
		f[y][0] = x;
		dep[y] = dep[x] + 1;
		dfs(y);
	}
}
int lca(int x, int y)
{
	if (x == y)
		return x;
	if (dep[x] < dep[y])
		swap(x, y);
	for (int i = 24; i >= 0; i--)
		if (dep[f[x][i]] > dep[y])
			x = f[x][i];
	if (x == y)
		return x;
	for (int i = 24; i >= 0; i--)
		if (f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	return f[x][0];
}
vector<int> G1[N];
int jump(int x, int fa)
{
	int stp = dep[x] - dep[fa] - 1;
	for (int i = 24; i >= 0; i--)
	{
		if (stp & (1 << i))
			x = f[x][i];
	}
	return x;
}
bool vis[N];
void work()
{
	cin >> n;
	for (int y = 2; y <= n; y++)
	{
		int x;
		cin >> x;
		G[x].push_back(y);
	}
	dfs(1);
	cin >> q;
	for (int t = 1; t <= q; t++)
	{
		cin >> m;
		vector<int> arr(m), vec;
		auto clear = [&]()
		{
			for (auto x : vec)
			{
				G1[x].clear();
				vis[x] = 0;
			}
		};
		for (int i = 0; i < m; i++)
			cin >> arr[i];
		bool ok = 1;
		for (int i = 1; i < m; i++)
		{
			int x = arr[i - 1], y = arr[i];
			if (dep[x] < dep[y])
			{
				ok = 0;
				break;
			}
			if (dep[x] != dep[y])
				continue;
			int anc = lca(x, y);
			int x1 = jump(x, anc);
			int x2 = jump(y, anc);
			vec.push_back(x1);
			vec.push_back(x2);
			G1[x1].push_back(x2);
		}
		if (!ok)
		{
			cout << "No\n";
			clear();
			continue;
		}
		auto checkRing = [&](auto &checkRing, int x)
		{
			if (vis[x])
				return false;
			vis[x] = true;
			for (auto y : G1[x])
			{
				if (!checkRing(checkRing, y))
					return false;
			}
			return true;
		};
		for (auto x : vec)
			if (ok && !vis[x] && !checkRing(checkRing, x))
			{
				ok = false;
				break;
			}
		cout << (ok ? "Yes\n" : "No\n");
		clear();
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t-- > 0)
	{
		work();
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3808kb

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:

No
Yes
No
No
No
No
No
No
No
No

result:

wrong answer expected YES, found NO [3rd token]