QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661371 | #8551. DFS Order 5 | LeNcyer# | WA | 35ms | 3756kb | C++20 | 1.7kb | 2024-10-20 15:57:14 | 2024-10-20 15:57:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
const int sz = 20;
int n, q;
vector<int> t[N];
int dep[N], f[N][sz];
void dfs (int x, int fa) {
f[x][0] = fa;
dep[x] = dep[fa] + 1;
for (int i = 1; i < sz; i ++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (auto y: t[x]) {
if (y == fa) continue;
dfs(y, x);
}
}
int get_lca (int x, int y) {
for (int i = sz - 1; i >= 0; i --) {
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (dep[f[y][i]] >= dep[x]) y = f[y][i];
}
if (x == y) return x;
for (int i = sz - 1; i >= 0; i --) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
void init () {
cin >> n >> q;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
t[u].push_back(v);
t[v].push_back(u);
}
}
int a[N];
void solve() {
init();
dfs(1, 0);
// cout << "debug\n";
while (q --) {
int k;
cin >> k;
for (int i = 1; i <= k; i ++) {
cin >> a[i];
}
// cout << q << ' ' << k << endl;
bool ok = 1;
for (int i = 2; i <= k; i ++) {
int fa = f[a[i]][0];
int lca = get_lca(a[i - 1], a[i]);
if (fa != lca) {
ok = 0;
break;
}
}
if (ok) cout << "Yes\n";
else cout << "No\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
// cin >> _;
while (_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3756kb
input:
6 7 1 2 1 3 2 4 3 5 2 6 2 4 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 6 1 2 6 4 3 5
output:
No No Yes No No Yes Yes
result:
ok 7 tokens
Test #2:
score: -100
Wrong Answer
time: 35ms
memory: 3716kb
input:
10 100000 7 2 1 7 7 10 8 6 8 7 1 3 4 5 9 5 5 8 8 8 9 7 2 8 1 6 1 4 8 3 5 2 6 7 10 3 9 9 1 1 1 8 10 3 2 9 3 8 7 3 7 5 6 2 8 5 9 1 6 3 4 6 2 1 3 5 8 9 2 4 9 1 3 2 1 5 5 8 5 1 7 9 10 5 2 9 2 6 4 10 6 3 8 3 4 5 8 2 8 4 9 4 10 1 2 4 3 3 6 3 1 3 6 1 1 6 8 3 1 3 7 3 2 3 9 1 5 4 3 7 8 10 9 4 2 3 10 2 5 4 3 ...
output:
No No No Yes No No No No Yes No No No No No No Yes No No No Yes No No No No No No No No No Yes No Yes No No No No No No Yes No No No No No Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No Yes No No Yes Yes No No No No Yes No No No No No No No No Yes No No No No No No N...
result:
wrong answer 20th words differ - expected: 'No', found: 'Yes'