QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#536363 | #8551. DFS Order 5 | QSteve_Paul | RE | 0ms | 65492kb | C++23 | 7.3kb | 2024-08-29 08:53:43 | 2024-08-29 08:53:43 |
Judging History
answer
#include <vector>
#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
struct SegmentTree
{
constexpr static int N = 1e6 + 5;
#define rson ((k << 1) + 1)
#define lson (k << 1)
#define me (k)
#define mid ((a[me].l + a[me].r) >> 1)
struct node
{
int l, r;
int sum;
int lazy;
node()
{
l = r = sum = 0;
lazy = -1;
}
};
vector<node> a = vector<node>(N * 4);
void update(int k)
{
a[me].sum = a[lson].sum + a[rson].sum;
}
void build(int k, int l, int r)
// 当前在k上,建树
{
a[me].l = l;
a[me].r = r;
if (l == r)
{
a[me].sum = 0;
return;
}
build(lson, a[me].l, mid);
build(rson, mid + 1, a[me].r);
update(k);
}
void pushdown(int k)
{
if (a[me].l == a[me].r)
{
a[me].lazy = -1;
return;
}
a[lson].sum = (a[lson].r - a[lson].l + 1) * a[me].lazy;
a[rson].sum = (a[rson].r - a[rson].l + 1) * a[me].lazy;
a[lson].lazy = a[me].lazy;
a[rson].lazy = a[me].lazy;
a[me].lazy = -1;
}
int query(int k, int idx)
{
if (a[me].lazy != -1)
pushdown(k);
if (a[me].l == idx && a[me].r == idx)
return a[me].sum;
if (idx <= mid)
return query(lson, idx);
return query(rson, idx);
}
void set_segment(int k, int l, int r, int x)
{
if (a[k].l == l && a[k].r == r)
{
a[k].sum = (r - l + 1) * x;
a[k].lazy = x;
return;
}
if (a[me].lazy != -1)
pushdown(k);
if (r <= mid)
set_segment(lson, l, r, x);
else if (l > mid)
set_segment(rson, l, r, x);
else
{
set_segment(lson, l, mid, x);
set_segment(rson, mid + 1, r, x);
}
update(k);
}
#undef rson
#undef lson
#undef me
#undef mid
};
void solve()
{
int n;
cin >> n;
int q;
cin >> q;
SegmentTree st;
st.build(1, 1, n);
vector<vector<int>> tree(n + 1);
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
tree[u].emplace_back(v);
tree[v].emplace_back(u);
}
tree[1].emplace_back(0);
vector<int> dfn(n + 1);
vector<int> ofn(n + 1);
vector<int> sz(n + 1);
vector<int> ffa(n + 1);
vector<int> depth(n + 1);
vector<int> hvy(n + 1);
vector<int> hvymn(n + 1);
vector<int> hvymx(n + 1);
vector<int> hvyid(n + 1, -1);
function<void(int, int)> dfs1 = [&](int node, int fa) -> void
{
depth[node] = depth[fa] + 1;
ffa[node] = fa;
sz[node] = 1;
for (const int& child : tree[node])
{
if (child == fa) continue;
dfs1(child, node);
sz[node] += sz[child];
}
};
dfs1(1, 0);
for (int i = 1; i <= n; i++)
{
int idx = 0;
int mx = -1;
for (const int& child : tree[i])
{
++idx;
if (child == ffa[i]) continue;
if (mx == -1) mx = child;
else
{
if (sz[child] > sz[mx])
mx = child;
}
}
if(mx != -1)
hvy[mx] = 1;
hvyid[i] = mx;
}
int dfncnt = 0;
function<void(int, int)> dfs2 = [&](int node, int fa) -> void
{
dfncnt++;
dfn[node] = dfncnt;
if (hvy[node])
{
if (hvy[fa])
hvymn[node] = hvymn[fa];
else
hvymn[node] = dfn[node];
hvymx[node] = dfn[node];
}
if (hvyid[node] != -1)
{
dfs2(hvyid[node], node);
hvymx[node] = hvymx[hvyid[node]];
}
for (const int& child : tree[node])
{
if (child == fa) continue;
if (child == hvyid[node]) continue;
dfs2(child, node);
}
ofn[node] = dfncnt;
};
dfs2(1, 0);
for (int i = 1; i <= n; i++)
{
int faidx = -1;
for (int j = 0; j < tree[i].size(); j++)
if (ffa[i] == tree[i][j])
faidx = j;
if(faidx != -1)
swap(tree[i][faidx], tree[i].back());
tree[i].pop_back();
sort(tree[i].begin(), tree[i].end(), [&](const int& nd1, const int& nd2)
{
return ofn[nd1] < ofn[nd2];
});
}
function<bool(int, int)> is_in_tree = [&](int node, int fa) -> bool
{
return dfn[node] >= dfn[fa] && dfn[node] <= ofn[fa];
};
function<void(int)> add_line = [&](int node) -> void
{
while (node != 0)
{
if (hvy[node])
{
int mn = hvymn[node];
st.set_segment(1, dfn[mn], dfn[node], 1);
node = mn;
}
else
{
st.set_segment(1, dfn[node], dfn[node], 1);
}
node = ffa[node];
}
};
vector<int> k;
while (q--)
{
int qq;
cin >> qq;
k.resize(qq + 1);
for (int i = 1; i <= qq; i++)
cin >> k[i];
// TODO: clear the SegmentTree
st.set_segment(1, 1, n, 0);
bool isok = true;
if (!is_in_tree(k[min(1 + sz[k[1]] - 1, qq)], k[1]))
isok = false;
add_line(k[1]);
for (int i = 2; i <= qq; i++)
{
if (!is_in_tree(k[min(i + sz[k[i]] - 1, qq)], k[i])) isok = false;
if (!isok) break;
int thisfa = ffa[k[i]];
if (!is_in_tree(k[i - 1], thisfa)) isok = false;
if (!isok) break;
// TODO: ensure it's not visited in SegmentTree
if (st.query(1, dfn[k[i]]))
isok = false;
if (!isok) break;
add_line(k[i]);
if (thisfa != k[i - 1])
{
if (dfn[k[i-1]] < dfn[tree[thisfa].front()] || dfn[k[i-1]] > ofn[tree[thisfa].back()]) isok = false;
if (!isok) break;
int l = 0;
int r = tree[thisfa].size() - 1;
while (l < r)
{
int mid = (l + r) / 2 ;
if (ofn[tree[thisfa][mid]] < dfn[k[i-1]]) l = mid + 1;
else r = mid;
}
int nearfa = tree[thisfa][l];
if(!is_in_tree(k[i-1], nearfa)) isok = false;
if(!isok) break;
// TODO: ensure the childs of nearfa and itself is visited
st.set_segment(1, dfn[nearfa], ofn[nearfa], 1);
}
}
if (isok) cout << "Yes\n";
else cout << "No\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solve();
}
/*
*
6 4
1 2
1 3
2 4
3 5
2 6
3 4 6 3
3 4 6 1
4 2 6 4 3
4 1 4 6 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 65492kb
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
Runtime Error
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 ...