QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422106 | #8720. BFS 序 0 | MaxDYF | ML | 2ms | 5616kb | C++23 | 3.1kb | 2024-05-26 19:27:29 | 2024-05-26 19:27:30 |
Judging History
answer
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 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 i = 1; i <= q; i++)
{
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] = false;
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: 100
Accepted
time: 2ms
memory: 5616kb
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
Memory Limit Exceeded
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...