QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #639342 | #8551. DFS Order 5 | spacetimewww | WA | 34ms | 11864kb | C++17 | 6.2kb | 2024-10-13 19:04:32 | 2024-10-13 19:04:32 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n, q;
const int N = 100005;
vector<int> g[N + 5];
int fa[N + 5][25];
int dep[N + 5];
int tr[N + 5];
int in[N + 5], out[N + 5];
int tot = 0;
int dfn[N + 5];
int sz[N + 5];
struct Fenwick{
int tr[N + 5] = {0};
int lowbit(int x){
return x & -x;
}
void add(int p, int x){
for (int i = p; i <= 100000; i += lowbit(i)){
tr[i] += x;
}
}
int query(int p){
int res = 0;
for (int i = p; i >= 1; i -= lowbit(i)){
res += tr[i];
}
return res;
}
void modify(int l, int r, int v){
add(l, v);
add(r + 1, -v);
}
int querySeg(int l, int r){
return query(r) - query(l - 1);
}
}fenwick[2];//0:sum(normal), 1:vis(sub)
void dfs(int u, int ffa){
tot++;
dfn[tot] = u;
in[u] = tot;
fa[u][0] = ffa;
sz[u] = 1;
for (int i = 1; (1 << i) + 1 <= dep[u]; i++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (auto v : g[u]){
if (v == ffa) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
out[u] = tot;
}
int lca(int x, int y){
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--){
if (dep[fa[x][i]] >= dep[y]){
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];
}
int getAnc(int x, int d){
int p = x;
for (int bit = 20; bit >= 0; bit--){
if (d >> bit & 1){
p = fa[p][bit];
}
}
return p;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
while (T--){
cin >> n >> q;
int ccnt = 0;
int tt = q;
vector<int> deg(n + 5);
vector< pair<int, int> > edge;
for (int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
edge.emplace_back(u, v);
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
vector<int> cnt(n + 5);
dep[1] = 1;
dfs(1, 0);
vector<int> son(n + 5);
for (int i = 1; i <= n; i++){
son[i] = deg[i] - (i != 1);
}
vector<int> vis(n + 5);
while (q--){
unordered_map<int, int> mp;
int tmp = 0;
int k;
cin >> k;
vector<int> b(k + 5);
for (int i = 1; i <= k; i++) cin >> b[i], vis[b[i]] = 1;
int flag = 0;
for (int i = 1; i <= k; i++){
cnt[b[i]]++;
if (cnt[b[i]] > 1) flag++;
}
for (int i = 1; i <= k; i++){
cnt[b[i]]--;
}
if (flag){
cout << "No" << endl;
continue;
}
vector< pair<int, int> > op[2];
for (int i = 1; i < k; i++){
int u = b[i], v = b[i + 1];
mp[u] = 1;
if (fenwick[1].query(in[u]) || fenwick[1].query(in[v])){
flag++;
break;
}
fenwick[0].add(in[u], 1);
op[0].emplace_back(in[u], 1);
// cout << "tmp = " << tmp << endl;
if (!son[u] && vis[u]){
tmp++;
}
// cout << "tmp = " << tmp << endl;
son[fa[u][0]]--;
if (!son[fa[u][0]] && vis[fa[u][0]]){
tmp++;
}
// cout << "tmp = " << tmp << endl;
// son[fa[v][0]]--;
// if (!son[fa[v][0]]){
// tmp++;
// }
if (dep[u] < dep[v]) {
if (u != fa[v][0]) {
flag++;
break;
}
}
else {
int l = lca(u, v);
if (!(u != 1 && deg[u] == 1 && l == fa[v][0])) {
flag++;
break;
}
int d = dep[u] - dep[l] - 1;
int x = getAnc(u, d);
if (mp.count(x)){
if (fenwick[0].querySeg(in[x], out[x]) != sz[x]){
flag++;
break;
}
}
else {
if (tmp != i) {
flag++;
break;
}
}
fenwick[1].modify(in[x], out[x], 1);
op[1].emplace_back(in[x], out[x]);
}
}
for (auto [lll, r] : op[0]){
fenwick[0].add(lll, -1);
}
for (auto [lll, r] : op[1]){
fenwick[1].modify(lll, r, -1);
}
for (int i = 1; i <= k; i++){
int pp = b[i];
son[pp] = deg[pp] - (pp != 1);
vis[pp] = 0;
pp = fa[b[i]][0];
son[pp] = deg[pp] - (pp != 1);
}
ccnt++;
if (tt == 100000 && ccnt == 46){
cout << n << ' ' << 1 << endl;
cout << edge.size() << endl;
for (auto [lll, rrr] : edge){
cout << lll << ' ' << rrr << endl;
}
cout << k << endl;
for (int i = 1; i <= k; i++) cout << b[i] << ' ';
cout << endl;
}
if (tt == 100000) continue;
if (flag) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
return 0;
}
/*
6 1
1 2
1 3
2 4
3 5
2 6
6 1 2 6 4 3 5
*/
/*
6 4
1 2
1 3
2 4
2 5
5 6
2 6 3
3 5 6 3
4 4 5 6 3
5 2 5 6 3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11864kb
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: 34ms
memory: 11092kb
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 No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No 10 1 9 7 2 1 7 7 10 8 6 8 7 1 3 4 5 9 5 5 8 1...
result:
wrong answer 4th words differ - expected: 'Yes', found: 'No'