QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#422136	#8720. BFS 序 0	MaxDYF	WA	148ms	55388kb	C++23	2.4kb	2024-05-26 20:27:24	2024-05-26 20:27:25

Judging History

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

[2024-05-26 20:27:25]
评测

测评结果：WA
用时：148ms
内存：55388kb

查看

[2024-05-26 20:27:24]
提交

answer

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

const int N = 3e5 + 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();
	}
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 5684kb

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
Yes
No
No
No
No
No
No
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #2:

score: -100

Wrong Answer

time: 148ms

memory: 55388kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
No
No
Yes
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
Yes
No
No
No
Yes
No
No
...

result:

wrong answer expected YES, found NO [2nd token]