QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#639 | #416474 | #8720. BFS 序 0 | MaxDYF | TLE_Automat | Failed. | 2024-05-26 20:52:18 | 2024-05-26 20:52:18 |
Details
Extra Test:
Accepted
time: 1ms
memory: 5612kb
input:
5 1 1 1 1 3 5 1 2 3 4 5 4 4 3 2 5 3 2 3 2
output:
Yes Yes No
result:
ok 3 token(s): yes count is 2, no count is 1
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416474 | #8720. BFS 序 0 | TLE_Automat | AC ✓ | 293ms | 55468kb | C++20 | 3.4kb | 2024-05-21 21:20:32 | 2024-05-21 21:20:33 |
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const int MAXN = 3e5 + 10;
int n, q;
int fa[MAXN][21];
vector<int> G[MAXN];
int dep[MAXN];
void dfs(int u, int d) {
dep[u] = d;
for (auto v : G[u]) {
dfs(v, d + 1);
}
}
int qlca(int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
int t = dep[x] - dep[y];
for (int i = 20; i >= 0; i--) {
if ((t >> i) & 1) {
x = fa[x][i];
}
}
if (x == y) {
return x;
}
for (int i = 20; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
void solve() {
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> fa[i][0];
G[fa[i][0]].push_back(i);
}
dfs(1, 0);
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= n; i++) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
vector indeg(n + 1, 0);
vector mpG(n + 1, vector<int>());
auto sol = [&]() -> void {
int m;
cin >> m;
vector p(m + 1, 0);
for (int i = 1; i <= m; i++) {
cin >> p[i];
}
for (int i = 1; i < m; i++) {
if (dep[p[i]] > dep[p[i + 1]]) {
cout << "No" << '\n';
return ;
}
}
set<int> s;
for (int i = 1; i < m; i++) {
int x = p[i], y = p[i + 1];
if (dep[x] != dep[y]) {
continue;
}
int lca = qlca(x, y);
// printf("x = %d, y = %d, lca = %d\n", x, y, lca);
for (int j = 20; j >= 0; j--) {
if (dep[fa[x][j]] > dep[lca]) {
x = fa[x][j];
}
}
for (int j = 20; j >= 0; j--) {
if (dep[fa[y][j]] > dep[lca]) {
y = fa[y][j];
}
}
// printf("u = %d, v = %d\n", x, y);
s.insert(x);
s.insert(y);
indeg[y]++;
mpG[x].push_back(y);
}
queue<int> q;
for (auto x : s) {
if (!indeg[x]) {
q.push(x);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : mpG[u]) {
indeg[v]--;
if (!indeg[v]) {
q.push(v);
}
}
}
bool flg = true;
for (auto x : s) {
if (indeg[x]) {
flg = false;
break;
}
}
cout << (flg ? "Yes" : "No") << '\n';
for (auto x : s) {
mpG[x].clear();
indeg[x] = 0;
}
};
cin >> q;
while (q--) {
sol();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
while (T--) solve();
return 0;
}