QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603744 | #8720. BFS 序 0 | reaepita | RE | 0ms | 0kb | C++14 | 1.9kb | 2024-10-01 18:45:39 | 2024-10-01 18:45:40 |
Judging History
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