QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884509 | #4408. 燃烧的呐球 | plmokn | 100 ✓ | 5655ms | 458796kb | C++14 | 11.1kb | 2025-02-06 08:55:49 | 2025-02-06 08:55:51 |
Judging History
answer
#include <bits/stdc++.h>
template <class T, class binary_op = std::plus<T>>
struct Segment_Tree {
struct node {
T u;
int lc, rc;
};
std::vector<node> tree;
binary_op comb;
T init;
int new_node() {
int x = tree.size();
tree.push_back({init, -1, -1});
return x;
}
int lc(int p) {
if (~tree[p].lc)
return tree[p].lc;
int x = new_node();
return tree[p].lc = x;
}
int rc(int p) {
if (~tree[p].rc)
return tree[p].rc;
int x = new_node();
return tree[p].rc = x;
}
Segment_Tree(const binary_op &comb = binary_op(), const T &init = T()) : comb(comb), init(init) {}
void modify(int p, int x, const T &y, int l, int r) {
tree[p].u = comb(tree[p].u, y);
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
modify(lc(p), x, y, l, mid);
if (mid + 1 <= x)
modify(rc(p), x, y, mid + 1, r);
return;
}
T query(int p, int ql, int qr, int l, int r) const {
if (!~p)
return init;
if (ql <= l && r <= qr)
return tree[p].u;
int mid = (l + r) >> 1;
if (qr <= mid)
return query(tree[p].lc, ql, qr, l, mid);
if (mid + 1 <= ql)
return query(tree[p].rc, ql, qr, mid + 1, r);
return comb(query(tree[p].lc, ql, qr, l, mid), query(tree[p].rc, ql, qr, mid + 1, r));
}
int merge(int p, int q, int l, int r) {
if (!~p || !~q)
return std::max(p, q);
int mid = (l + r) >> 1;
tree[p].u = comb(tree[p].u, tree[q].u);
tree[p].lc = merge(tree[p].lc, tree[q].lc, l, mid);
tree[p].rc = merge(tree[p].rc, tree[q].rc, mid + 1, r);
return p;
}
};
template <class T, class binary_op = std::plus<T>>
struct Binary_Indexed_Tree_like {
int n;
std::vector<T> tree, tree2;
binary_op comb;
T init;
std::stack<std::pair<std::vector<std::pair<int, T>>, std::vector<std::pair<int, T>>>> st;
Binary_Indexed_Tree_like(int n, const binary_op &comb = binary_op(), const T &init = T()) : n(n), tree(n, init), tree2(n, init), comb(comb), init(init) {}
static constexpr int lowbit(int x) { return x & -x; }
void add(int x, const T &y) {
std::pair<std::vector<std::pair<int, T>>, std::vector<std::pair<int, T>>> tmp;
for (int i = x + 1; i <= n; i += lowbit(i))
tmp.first.emplace_back(i - 1, tree[i - 1]), tree[i - 1] = comb(tree[i - 1], y);
for (int i = x; i > 0; i -= lowbit(i))
tmp.second.emplace_back(i - 1, tree2[i - 1]), tree2[i - 1] = comb(tree2[i - 1], y);
st.push(std::move(tmp));
return;
}
T sum(int l, int r) const {
T ans(init);
for (int i = l; i && i + lowbit(i) <= r + 1; i += lowbit(i))
ans = comb(ans, tree2[i - 1]);
for (int i = r + 1; i && i - lowbit(i) >= l; i -= lowbit(i))
ans = comb(ans, tree[i - 1]);
return ans;
}
void undo() {
for (const auto &i : st.top().first)
tree[i.first] = i.second;
for (const auto &i : st.top().second)
tree2[i.first] = i.second;
st.pop();
return;
}
};
struct tree {
int n;
std::vector<std::vector<int>> children;
std::vector<int> dfn, parent, senior, siz, top, seq, qes;
int doc;
tree(int n) : n(n), children(n) {}
void add_edge(int u, int v) {
children[u].push_back(v);
return;
}
void dfs(int x) {
siz[x] = 1;
senior[x] = -1;
for (int y : children[x]) {
parent[y] = x;
dfs(y);
siz[x] += siz[y];
if (!~senior[x] || siz[y] > siz[senior[x]])
senior[x] = y;
}
return;
}
void dfs(int x, int t) {
qes.push_back(x);
dfn[x] = doc++;
top[x] = t;
if (~senior[x])
dfs(senior[x], t);
for (int y : children[x])
if (y != senior[x])
dfs(y, y);
seq.push_back(x);
return;
}
void build() {
dfn.assign(n, -1);
parent.assign(n, -1);
senior.assign(n, -1);
siz.assign(n, 0);
top.assign(n, -1);
doc = 0;
dfs(0);
dfs(0, 0);
return;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m;
std::cin >> n >> m;
tree g(n);
for (int i = 1; i < n; ++i) {
int x;
std::cin >> x;
--x;
g.add_edge(x, i);
}
g.build();
std::vector<std::pair<std::vector<int>, std::vector<int>>> s(n);
std::vector<std::pair<int, int>> c(m);
for (int i = 0; i < m; ++i)
std::cin >> c[i].first >> c[i].second, --c[i].first, --c[i].second, s[c[i].first].first.push_back(i), s[c[i].second].second.push_back(i);
std::vector<int> pa(m);
std::iota(pa.begin(), pa.end(), 0);
std::function<int(int)> find_set = [&](int x) -> int {
if (x == pa[x])
return x;
return pa[x] = find_set(pa[x]);
};
static constexpr std::pair<int, int> _(std::numeric_limits<int>::max(), -1);
typedef std::remove_const_t<decltype(_)> __t;
static constexpr std::pair<__t, __t> __(_, _);
typedef std::remove_const_t<decltype(__)> ___t;
auto take = [](const ___t &x, const ___t &y) -> ___t { return {std::min(x.first, y.first), x.first.second == y.first.second ? std::min(x.second, y.second) : (x.first == std::min(x.first, y.first) ? std::min(x.second, y.first) : std::min(x.first, y.second))}; };
auto add = [](const __t &x, int y) -> __t { return {x.first == std::numeric_limits<int>::max() ? x.first : x.first + y, x.second}; };
auto choose = [](const ___t &x, int y) -> __t { return x.first.second == y ? x.second : x.first; };
long long ans = 0;
while (std::adjacent_find(pa.begin(), pa.end(), [&](int x, int y) -> bool { return find_set(x) != find_set(y); }) != pa.end()) {
std::vector<__t> d(m, _);
___t p(__);
for (int i = 0; i < m; ++i)
p = take(p, {{g.siz[c[i].first] + g.siz[c[i].second], find_set(i)}, _});
for (int i = 0; i < m; ++i)
d[find_set(i)] = std::min(d[find_set(i)], add(choose(p, find_set(i)), g.siz[c[i].first] + g.siz[c[i].second]));
std::vector<std::pair<___t, ___t>> f(n, {__, __});
for (int i : g.seq) {
for (int j : s[i].first)
f[i].first = take(f[i].first, {{g.siz[c[j].second] - g.siz[c[j].first], find_set(j)}, _});
for (int j : s[i].second)
f[i].second = take(f[i].second, {{g.siz[c[j].first] - g.siz[c[j].second], find_set(j)}, _});
for (int j : g.children[i])
f[i].first = take(f[i].first, f[j].first), f[i].second = take(f[i].second, f[j].second);
for (int j : s[i].first)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f[i].first, find_set(j)), g.siz[c[j].first] + g.siz[c[j].second]));
for (int j : s[i].second)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f[i].second, find_set(j)), g.siz[c[j].first] + g.siz[c[j].second]));
}
f.assign(n, {__, __});
for (int i : g.qes) {
for (int j : s[i].first)
f[i].first = take(f[i].first, {{g.siz[c[j].first] + g.siz[c[j].second], find_set(j)}, _});
for (int j : s[i].second)
f[i].second = take(f[i].second, {{g.siz[c[j].first] + g.siz[c[j].second], find_set(j)}, _});
for (int j : g.children[i])
f[j].first = take(f[j].first, f[i].first), f[j].second = take(f[j].second, f[i].second);
for (int j : s[i].first)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f[i].first, find_set(j)), g.siz[c[j].second] - g.siz[c[j].first]));
for (int j : s[i].second)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f[i].second, find_set(j)), g.siz[c[j].first] - g.siz[c[j].second]));
}
Segment_Tree<___t, decltype(take)> f2(take, __);
std::vector<int> p2(n, -1);
for (int i : g.seq) {
for (int j : g.children[i])
p2[i] = f2.merge(p2[i], p2[j], 0, n - 1);
p2[i] = ~p2[i] ? p2[i] : f2.new_node();
for (int j : s[i].first)
f2.modify(p2[i], g.dfn[c[j].second], {{-g.siz[c[j].first] - g.siz[c[j].second], find_set(j)}, _}, 0, n - 1);
for (int j : s[i].first)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f2.query(p2[i], g.dfn[c[j].second], g.dfn[c[j].second] + g.siz[c[j].second] - 1, 0, n - 1), find_set(j)), g.siz[c[j].first] + g.siz[c[j].second]));
}
Binary_Indexed_Tree_like<___t, decltype(take)> f3(n, take, __);
std::vector<int> p3(n);
for (int i : g.qes) {
while (f3.st.size() > (~g.parent[i] ? p3[g.parent[i]] : 0))
f3.undo();
for (int j : s[i].first)
f3.add(g.dfn[c[j].second], {{g.siz[c[j].first] - g.siz[c[j].second], find_set(j)}, _});
p3[i] = f3.st.size();
for (int j : s[i].first)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f3.sum(g.dfn[c[j].second], g.dfn[c[j].second] + g.siz[c[j].second] - 1), find_set(j)), g.siz[c[j].second] - g.siz[c[j].first]));
}
for (int i : g.qes) {
while (f3.st.size() > (~g.parent[i] ? p3[g.parent[i]] : 0))
f3.undo();
for (int j : s[i].second)
f3.add(g.dfn[c[j].first], {{g.siz[c[j].second] - g.siz[c[j].first], find_set(j)}, _});
p3[i] = f3.st.size();
for (int j : s[i].second)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(f3.sum(g.dfn[c[j].first], g.dfn[c[j].first] + g.siz[c[j].first] - 1), find_set(j)), g.siz[c[j].first] - g.siz[c[j].second]));
}
auto upward = [&](int x) -> ___t {
___t ans(__);
while (~x) {
ans = take(ans, f3.sum(g.dfn[g.top[x]], g.dfn[x]));
x = g.parent[g.top[x]];
}
return ans;
};
for (int i : g.qes) {
while (f3.st.size() > (~g.parent[i] ? p3[g.parent[i]] : 0))
f3.undo();
for (int j : s[i].first)
f3.add(g.dfn[c[j].second], {{g.siz[c[j].first] + g.siz[c[j].second], find_set(j)}, _});
p3[i] = f3.st.size();
for (int j : s[i].first)
d[find_set(j)] = std::min(d[find_set(j)], add(choose(upward(c[j].second), find_set(j)), -g.siz[c[j].first] - g.siz[c[j].second]));
}
for (int i = 0; i < m; ++i)
if (i == find_set(i) && d[i].first < std::numeric_limits<int>::max() && find_set(i) != find_set(d[i].second))
pa[find_set(i)] = find_set(d[i].second), ans += d[i].first;
}
std::cout << ans << '\n';
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 7ms
memory: 4196kb
Test #2:
score: 10
Accepted
time: 7ms
memory: 4104kb
Test #3:
score: 10
Accepted
time: 8ms
memory: 4196kb
Test #4:
score: 10
Accepted
time: 7ms
memory: 4048kb
Test #5:
score: 10
Accepted
time: 7ms
memory: 3944kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 2003ms
memory: 230844kb
Test #7:
score: 10
Accepted
time: 1232ms
memory: 217588kb
Test #8:
score: 10
Accepted
time: 836ms
memory: 226480kb
Test #9:
score: 10
Accepted
time: 843ms
memory: 220504kb
Test #10:
score: 10
Accepted
time: 1169ms
memory: 215596kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 3236ms
memory: 253676kb
Test #12:
score: 10
Accepted
time: 2097ms
memory: 240820kb
Test #13:
score: 10
Accepted
time: 1611ms
memory: 243188kb
Test #14:
score: 10
Accepted
time: 1579ms
memory: 254820kb
Test #15:
score: 10
Accepted
time: 2046ms
memory: 253300kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 705ms
memory: 13088kb
Test #17:
score: 20
Accepted
time: 747ms
memory: 13612kb
Test #18:
score: 20
Accepted
time: 441ms
memory: 18316kb
Test #19:
score: 20
Accepted
time: 571ms
memory: 13092kb
Test #20:
score: 20
Accepted
time: 696ms
memory: 13000kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 5586ms
memory: 458796kb
Test #22:
score: 10
Accepted
time: 5655ms
memory: 450112kb
Test #23:
score: 10
Accepted
time: 5629ms
memory: 450016kb
Test #24:
score: 10
Accepted
time: 5550ms
memory: 450028kb
Test #25:
score: 10
Accepted
time: 5610ms
memory: 449988kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1642ms
memory: 297944kb
Test #27:
score: 10
Accepted
time: 1623ms
memory: 298024kb
Test #28:
score: 10
Accepted
time: 1636ms
memory: 298016kb
Test #29:
score: 10
Accepted
time: 1614ms
memory: 298012kb
Test #30:
score: 10
Accepted
time: 1574ms
memory: 298008kb
Subtask #7:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #31:
score: 30
Accepted
time: 4692ms
memory: 314652kb
Test #32:
score: 30
Accepted
time: 2846ms
memory: 322864kb
Test #33:
score: 30
Accepted
time: 2197ms
memory: 306444kb
Test #34:
score: 30
Accepted
time: 2254ms
memory: 311644kb
Test #35:
score: 30
Accepted
time: 2761ms
memory: 310100kb
Test #36:
score: 30
Accepted
time: 4746ms
memory: 325252kb
Test #37:
score: 30
Accepted
time: 2832ms
memory: 322868kb
Test #38:
score: 30
Accepted
time: 2233ms
memory: 306440kb
Test #39:
score: 30
Accepted
time: 2255ms
memory: 311652kb
Test #40:
score: 30
Accepted
time: 2729ms
memory: 320684kb