QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661741 | #8551. DFS Order 5 | LeNcyer | WA | 2ms | 9788kb | C++17 | 4.3kb | 2024-10-20 17:53:25 | 2024-10-20 17:53:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
const int lim = 20;
class Segment{
private:
struct Node {
int val, tag;
} node[N << 2];
public:
void push_up (int p) {
node[p].val = node[p << 1].val | node[p << 1 | 1].val;
}
void build (int s, int t, int p = 1) {
node[p].tag = -1;
if (s == t) {
node[p].val = 0;
return;
}
int mid = (s + t) >> 1;
build(s, mid, p << 1);
build(mid + 1, t, p << 1 | 1);
push_up(p);
}
void push_down (int p) {
if (node[p].tag != -1) {
node[p << 1].tag = node[p << 1].val = node[p].tag;
node[p << 1 | 1].tag = node[p << 1 | 1].val = node[p].tag;
node[p].tag = -1;
}
}
void update (int l, int r, int v, int s, int t, int p = 1) {
if (l <= s && t <= r) {
node[p].val = v;
node[p].tag = v;
return;
}
push_down(p);
int mid = (s + t) >> 1;
if (l <= mid) update(l, r, v, s, mid, p << 1);
if (mid < r) update(l, r, v, mid + 1, t, p << 1 | 1);
push_up(p);
}
int query (int l, int r, int s, int t, int p = 1) {
if (l <= s && t <= r) return node[p].val;
push_down(p);
int mid = (s + t) >> 1;
int res = 0;
if (l <= mid) res = query(l, r, s, mid, p << 1);
if (mid < r) res |= query(l, r, mid + 1, t, p << 1 | 1);
push_up(p);
return res;
}
};
Segment seg;
int n, q;
vector<int> t[N];
int dep[N], f[N][lim];
int sz[N], dfn[N], hs[N], tp[N], totdfn = 0;
void dfs (int x, int fa) {
f[x][0] = fa;
dep[x] = dep[fa] + 1;
sz[x] = 1;
for (int i = 1; i < lim; i ++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
hs[x] = 0;
for (auto y: t[x]) {
if (y == fa) continue;
dfs(y, x);
sz[x] += sz[y];
if(sz[y] > sz[hs[x]]) hs[x] = y;
}
}
void dfs2 (int x, int fa, int top) {
dfn[x] = ++ totdfn;
tp[x] = top;
if (hs[x]) dfs2(hs[x], x, top);
for (auto y: t[x]) {
if (y == fa || y == hs[x]) continue;
dfs2(y, x, y);
}
}
int get (int x, int len) {
int cur = x;
for (int i = 0; i < lim; i ++) {
if ((len >> i) & 1) cur = f[cur][i];
}
return cur;
}
int get_lca (int x, int y) {
for (int i = lim - 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 = lim - 1; i >= 0; i --) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int cal (int x, int y) {
// cout << "cal: " << x << ' ' << y << endl;
int res = 0;
while (dep[x] >= dep[y]) {
int l = dfn[tp[x]], r = dfn[x];
if (dep[y] > dep[tp[x]]) l = dfn[y];
res |= seg.query(l, r, 1, n);
if (res) return res;
x = f[tp[x]][0];
}
return res;
}
void col (int x, int y) {
while (dep[x] >= dep[y]) {
int l = dfn[tp[x]], r = dfn[x];
if (dep[y] > dep[tp[x]]) l = dfn[y];
seg.update(l, r, 1, 1, n);
x = f[tp[x]][0];
}
return;
}
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], pos[N];
void solve() {
init();
dfs(1, 0);
dfs2(1, 0, 1);
seg.build(1, n);
// for (int i = 1; i <= n; i ++) {
// cout << i << ' ' << hs[i] << ' ' << tp[i] << endl;
// }
// cout << "debug\n";
for (int _ = 1; _ <= q; _ ++) {
int k;
cin >> k;
for (int i = 1; i <= k; i ++) {
cin >> a[i];
pos[a[i]] = i;
}
if (_ == 30) {
cout << k << ':';
for (int i = 1; i <= k; i ++) cout << a[i] << ',';
return;
}
seg.update(1, n, 0, 1, n);
bool ok = 1;
if (sz[a[1]] > 1) {
int r = min(k, sz[a[1]]);
if (get_lca(a[1], a[r]) != a[1]) {
ok = 0;
}
}
for (int i = 2; i <= k; i ++) {
int r = min(k, i + sz[a[i]] - 1);
if (get_lca(a[i], a[r]) != a[i]) {
ok = 0;
break;
}
int fa = f[a[i]][0];
if (fa == a[i - 1]) continue;
int lca = get_lca(a[i - 1], a[i]);
if (fa != lca) {
ok = 0;
break;
}
int u = a[i - 1], v = get(a[i - 1], dep[a[i - 1]] - dep[fa] - 1);
if (cal(u, v) || cal(a[i], a[i])) {
ok = 0;
break;
}
col(u, v);
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9712kb
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: 2ms
memory: 9788kb
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 No No No No No No No No No No 3:5,6,10,
result:
wrong answer 30th words differ - expected: 'No', found: '3:5,6,10,'