QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #423669 | #8720. BFS 序 0 | kjhhjki# | Compile Error | / | / | C++20 | 6.6kb | 2024-05-28 14:53:15 | 2024-05-28 14:53:19 |
Judging History
answer
#include <bits/stdc++.h>
#define For(i, a, b) for(i32 i = (a), endi = (b); i <= endi; ++i)
#define foR(i, a, b) for(i32 i = (a), endi = (b); i >= endi; --i)
using i32 = int;
using i64 = long long;
struct HLD
{
i32 n, t = 0;
std::vector<i32> sz, top, dep, pre, dfn, out, seq;
std::vector<std::vector<i32>> adj;
void init(i32 _n = 0)
{
n = _n; t = 0;
sz.assign(n+1, 1); seq.assign(n+1, 0);
dep = pre = top = dfn = out = seq;
adj.assign(n+1, std::vector<i32>());
}
HLD(i32 n = 0) { init(n); }
void addEdge(i32 u, i32 v) { adj[u].push_back(v); adj[v].push_back(u); }
void work(i32 rt = 1)
{
pre[rt] = 0; dep[rt] = 1; top[rt] = rt;
dfs1(rt); dfs2(rt);
}
void dfs1(i32 u)
{
if(pre[u]) adj[u].erase(find(adj[u].begin(), adj[u].end(), pre[u]));
sz[u] = 1;
for(auto &v: adj[u])
{
pre[v] = u; dep[v] = dep[u] + 1;
dfs1(v); sz[u] += sz[v];
if(sz[v] > sz[adj[u][0]]) std::swap(v, adj[u][0]);
}
}
void dfs2(i32 u)
{
dfn[u] = ++t; seq[t] = u;
for(auto v: adj[u])
top[v] = (v == adj[u][0]? top[u]: v),
dfs2(v);
out[u] = t;
}
i32 lca(i32 u, i32 v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) v = pre[top[v]];
else u = pre[top[u]];
}
return dep[u] < dep[v]? u: v;
}
i32 dis(i32 u, i32 v) { return dep[u] + dep[v] - dep[lca(u, v)] * 2; }
i32 jump(i32 u, i32 k)
{
if(dep[u] < k) return 0;
while(dep[u] - dep[top[u]] < k) k -= dep[u] - dep[top[u]] + 1, u = pre[top[u]];
return seq[dfn[u]-k];
}
};
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
i32 n;
std::cin >> n;
HLD hld(n);
For(i, 2, n)
{
i32 p;
std::cin >> p;
hld.addEdge(i, p);
}
hld.work();
std::vector<std::vector<i32>> adj(n+1);
std::vector<i32> in(n+1);
std::set<i32> used;
i32 q;
std::cin >> q;
while(q--)
{
i32 m;
std::cin >> m;
std::vector<i32> a(m+1);
used.clear();
bool flag = true;
For(i, 1, m)
{
std::cin >> a[i];
if(i == 1) continue;
if(a[i] == a[i-1] || hld.dep[a[i]] < hld.dep[a[i-1]]) flag = false;
if(hld.dep[a[i]] == hld.dep[a[i-1]])
{
i32 lca = hld.lca(a[i], a[i-1]);
i32 u = hld.jump(a[i-1], hld.dep[a[i-1]] - hld.dep[lca] - 1);
i32 v = hld.jump(a[i], hld.dep[a[i]] - hld.dep[lca] - 1);
used.insert(u); used.insert(v);
adj[u].push_back(v); ++in[v];
}
}
i32 cnt(0);
std::queue<i32> q;
for(auto u: used) if(!in[u]) q.push(u);
while(!q.empty())
{
i32 u = q.front(); q.pop(); ++cnt;
for(auto v: adj[u])
if(!--in[v])
q.push(v);
}
flag &= (cnt == i32(used.size()));
std::cout << (flag? "Yes": "No") << '\n';
for(auto u: used) adj[u].clear(), in[u] = 0;
}
return 0;
}#include <bits/stdc++.h>
#define For(i, a, b) for(i32 i = (a), endi = (b); i <= endi; ++i)
#define foR(i, a, b) for(i32 i = (a), endi = (b); i >= endi; --i)
using i32 = int;
using i64 = long long;
struct HLD
{
i32 n, t = 0;
std::vector<i32> sz, top, dep, pre, dfn, out, seq;
std::vector<std::vector<i32>> adj;
HLD(i32 n = 0) { init(n); }
void init(i32 _n = 0)
{
n = _n; t = 0;
sz.assign(n+1, 1); seq.assign(n+1, 0);
dep = pre = top = dfn = out = seq;
adj.assign(n+1, std::vector<i32>());
}
void addEdge(i32 u, i32 v) { adj[u].push_back(v); adj[v].push_back(u); }
void work(i32 rt = 1)
{
pre[rt] = 0; dep[rt] = 1; top[rt] = rt;
dfs1(rt); dfs2(rt);
}
void dfs1(i32 u)
{
if(pre[u]) adj[u].erase(find(adj[u].begin(),adj[u].end(),pre[u]));
sz[u] = 1;
for(auto &v: adj[u])
{
pre[v] = u; dep[v] = dep[u] + 1;
dfs1(v); sz[u] += sz[v];
if(sz[v] > sz[adj[u][0]]) std::swap(v,adj[u][0]);
}
}
void dfs2(i32 u)
{
dfn[u] = ++t; seq[t] = u;
for(auto v: adj[u])
{
top[v] = (v == adj[u][0] ? top[u] : v);
dfs2(v);
}
out[u] = t;
}
i32 lca(i32 u, i32 v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) v = pre[top[v]];
else u = pre[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
i32 dis(i32 u, i32 v) { return dep[u] + dep[v] - 2 * dep[lca(u,v)]; }
i32 jump(i32 u, i32 k)
{
if(dep[u] < k) return 0;
while(dep[u] - dep[top[u]] < k) k -= dep[u] - dep[top[u]] + 1, u = pre[top[u]];
return seq[dfn[u]-k];
}
};
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
i32 n;
std::cin >> n;
HLD hld(n);
For(i, 2, n)
{
i32 p;
std::cin >> p;
hld.addEdge(i, p);
}
hld.work();
std::vector<std::vector<i32>> adj(n+1);
std::vector<i32> in(n+1);
std::set<i32> used;
i32 q;
std::cin >> q;
while(q--)
{
i32 m;
std::cin >> m;
std::vector<i32> a(m+1);
used.clear();
bool flag = true;
For(i, 1, m)
{
std::cin >> a[i];
if(i == 1) continue;
if(a[i] == a[i-1] || hld.dep[a[i]] < hld.dep[a[i-1]]) flag = false;
if(hld.dep[a[i]] == hld.dep[a[i-1]])
{
i32 lca = hld.lca(a[i], a[i-1]);
i32 u = hld.jump(a[i-1], hld.dep[a[i-1]] - hld.dep[lca] - 1);
i32 v = hld.jump(a[i], hld.dep[a[i]] - hld.dep[lca] - 1);
used.insert(u); used.insert(v);
adj[u].push_back(v); ++in[v];
}
}
i32 cnt(0);
std::queue<i32> q;
for(auto u: used) if(!in[u]) q.push(u);
while(!q.empty())
{
i32 u = q.front(); q.pop(); ++cnt;
for(auto v: adj[u])
if(!--in[v])
q.push(v);
}
flag &= (cnt == i32(used.size()));
std::cout << (flag? "Yes": "No") << '\n';
for(auto u: used) adj[u].clear(), in[u] = 0;
}
return 0;
}
Details
answer.code:121:2: error: stray ‘#’ in program
121 | }#include <bits/stdc++.h>
| ^
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:12: error: ‘bits’ was not declared in this scope
121 | }#include <bits/stdc++.h>
| ^~~~
answer.code:121:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
121 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:121:3: error: ‘include’ does not name a type
121 | }#include <bits/stdc++.h>
| ^~~~~~~
answer.code:128:8: error: redefinition of ‘struct HLD’
128 | struct HLD
| ^~~
answer.code:8:8: note: previous definition of ‘struct HLD’
8 | struct HLD
| ^~~
answer.code:188:5: error: redefinition of ‘int main()’
188 | int main()
| ^~~~
answer.code:66:5: note: ‘int main()’ previously defined here
66 | int main()
| ^~~~