QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884465#4408. 燃烧的呐球plmokn100 ✓6269ms458668kbC++1411.5kb2025-02-06 08:36:542025-02-06 08:36:57

Judging History

This is the latest submission verdict.

  • [2025-02-06 08:36:57]
  • Judged
  • Verdict: 100
  • Time: 6269ms
  • Memory: 458668kb
  • [2025-02-06 08:36:54]
  • Submitted

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;
    }
    bool in(int x, int y) {
        return dfn[y] <= dfn[x] && dfn[x] <= dfn[y] + siz[y] - 1;
    }
    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]));
        }
        std::vector<std::tuple<int, int, int>> e;
        for (int i = 0; i < m; ++i)
            if (i == find_set(i) && d[i].first < std::numeric_limits<int>::max())
                e.emplace_back(i, d[i].second, d[i].first);
        std::sort(e.begin(), e.end(), [](const std::tuple<int, int, int> &x, const std::tuple<int, int, int> &y) -> bool { return std::get<2>(x) < std::get<2>(y); });
        for (auto [u, v, w] : e)
            if (find_set(u) != find_set(v))
                pa[find_set(u)] = find_set(v), ans += w;
    }
    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: 6ms
memory: 3976kb

Test #3:

score: 10
Accepted
time: 7ms
memory: 4040kb

Test #4:

score: 10
Accepted
time: 7ms
memory: 4196kb

Test #5:

score: 10
Accepted
time: 7ms
memory: 4196kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 2060ms
memory: 230724kb

Test #7:

score: 10
Accepted
time: 1296ms
memory: 219120kb

Test #8:

score: 10
Accepted
time: 910ms
memory: 226452kb

Test #9:

score: 10
Accepted
time: 914ms
memory: 217916kb

Test #10:

score: 10
Accepted
time: 1294ms
memory: 217248kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 3503ms
memory: 253680kb

Test #12:

score: 10
Accepted
time: 2321ms
memory: 240816kb

Test #13:

score: 10
Accepted
time: 1666ms
memory: 243060kb

Test #14:

score: 10
Accepted
time: 1731ms
memory: 254816kb

Test #15:

score: 10
Accepted
time: 2261ms
memory: 251184kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 604ms
memory: 13456kb

Test #17:

score: 20
Accepted
time: 745ms
memory: 14072kb

Test #18:

score: 20
Accepted
time: 462ms
memory: 18364kb

Test #19:

score: 20
Accepted
time: 589ms
memory: 12648kb

Test #20:

score: 20
Accepted
time: 606ms
memory: 13172kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 6236ms
memory: 458668kb

Test #22:

score: 10
Accepted
time: 6247ms
memory: 452608kb

Test #23:

score: 10
Accepted
time: 6269ms
memory: 452628kb

Test #24:

score: 10
Accepted
time: 6141ms
memory: 452628kb

Test #25:

score: 10
Accepted
time: 6165ms
memory: 452620kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1771ms
memory: 308608kb

Test #27:

score: 10
Accepted
time: 1774ms
memory: 298020kb

Test #28:

score: 10
Accepted
time: 1780ms
memory: 308544kb

Test #29:

score: 10
Accepted
time: 1807ms
memory: 308596kb

Test #30:

score: 10
Accepted
time: 1808ms
memory: 297976kb

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: 5068ms
memory: 314632kb

Test #32:

score: 30
Accepted
time: 3166ms
memory: 322868kb

Test #33:

score: 30
Accepted
time: 2498ms
memory: 306448kb

Test #34:

score: 30
Accepted
time: 2481ms
memory: 311576kb

Test #35:

score: 30
Accepted
time: 3111ms
memory: 310104kb

Test #36:

score: 30
Accepted
time: 5169ms
memory: 325160kb

Test #37:

score: 30
Accepted
time: 3110ms
memory: 322800kb

Test #38:

score: 30
Accepted
time: 2508ms
memory: 306448kb

Test #39:

score: 30
Accepted
time: 2508ms
memory: 320176kb

Test #40:

score: 30
Accepted
time: 3059ms
memory: 318632kb