QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642222 | #8551. DFS Order 5 | youthpaul | WA | 30ms | 3612kb | C++20 | 3.8kb | 2024-10-15 11:58:52 | 2024-10-15 11:58:52 |
Judging History
answer
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3f;
const long long INFLL=1e18;
typedef long long ll;
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n + 5, T{});
}
void update(int p, const T &v) { //在位置 p 加 v
while(p <= n){
a[p] += v;
p += p & -p;
}
}
T query(int p) {
T ans{};
while(p > 0){
ans += a[p];
p -= p & -p;
}
return ans;
}
T rangeSum(int l, int r) {
return query(r) - query(l - 1); //前缀和
}
int find_first(T sum){ //找到第一个 query(p) >= sum 的位置 p
int p = 0;
T val = 0;
for(int i = std::__lg(n); i >= 0; --i)
if((p | 1 << i) <= n && val + a[p | 1 << i] < sum){
p |= 1 << i;
val += a[p];
}
return p + 1;
}
int find_last(T sum){ //找到最后一个 query(p) <= sum 的位置 p
int p = 0;
T val = 0;
for(int i = std::__lg(n); i >= 0; --i)
if((p | 1 << i) <= n && val + a[p | 1 << i] <= sum){
p |= 1 << i;
val += a[p];
}
return p;
}
};
const int N = 100005;
const int K = 17;
std::vector<int> g[N];
int f[N][K + 1];
int h[N];
int dfn[N];
int up[N];
int tot;
int sz[N];
void dfs0(int u, int fa){
h[u] = h[fa] + 1;
f[u][0] = fa;
dfn[u] = ++tot;
sz[u] = 1;
for(int k = 1; (1 << k) <= h[u]; ++k)
f[u][k] = f[f[u][k - 1]][k - 1];
for(auto v : g[u])
if(v != fa){
dfs0(v, u);
sz[u] += sz[v];
}
up[u] = tot;
}
int lca(int u, int v){
if(h[u] < h[v]) std::swap(u, v);
for(int k = K; k >= 0; --k)
if(h[u] - (1 << k) >= h[v])
u = f[u][k];
if(u == v) return u;
for(int k = K; k >= 0; --k)
if(f[u][k] != f[v][k]){
u = f[u][k];
v = f[v][k];
}
return f[u][0];
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, q;
std::cin >> n >> q;
fore(i, 1, n){
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs0(1, 0);
Fenwick<int> fen(n);
int Q = q;
int C = 0;
while(q--){
++C;
int m;
std::cin >> m;
std::vector<int> a(m);
fore(i, 0, m) std::cin >> a[i];
std::vector<int> p;
if(C == 899){
std::cout << m << ' ';
for(auto x : a) std::cout << x << ' ';
}
auto check = [&]() -> bool {
if(m == 1) return true;
p.push_back(dfn[a[0]]);
fen.update(dfn[a[0]], 1);
if(a[0] != 1){
p.push_back(1);
fen.update(1, 1);
}
fore(i, 1, m){
int u = a[i - 1], w = a[i];
if(fen.rangeSum(dfn[w], up[w])) return false;
if(f[w][0] == u){
fen.update(dfn[w], 1);
p.push_back(dfn[w]);
continue;
}
if(fen.rangeSum(dfn[u], up[u]) != sz[u]) return false;
if(lca(u, f[w][0]) == f[w][0] && lca(u, w) != w){
fen.update(dfn[w], 1);
p.push_back(dfn[w]);
continue;
}
return false;
}
return true;
};
bool tag = check();
if(Q < 100) std::cout << (tag ? "Yes" : "No") << endl;
for(auto x : p) fen.update(x, -1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
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: 30ms
memory: 3572kb
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:
3 5 4 10
result:
wrong answer 1st words differ - expected: 'No', found: '3'