cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/Manual/utpc2012_12.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * 東京大学プログラミングコンテスト2012-L じょうしょうツリー
 * https://atcoder.jp/contests/utpc2012/submissions/52989718
 */

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Utility/SlopeTrick.hpp"

#include <iostream>
#include <vector>

using namespace zawa;

void solve() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> C(N), depth(N);
    std::cin >> C[0];
    std::vector<std::vector<int>> g(N);
    for (int i{1} ; i < N ; i++) {
        int P;
        std::cin >> P >> C[i];
        P--;
        g[P].push_back(i);
        depth[i] = depth[P] + 1;
        C[i] += depth[i];
    }
    std::vector<SlopeTrick<int, long long>> st(N);
    auto dfs{[&](auto dfs, int v) -> void {
        for (auto x : g[v]) {
            dfs(dfs, x);
            st[x].prefixMin();
            if (st[v].size() < st[x].size()) {
                std::swap(st[v], st[x]);
            }
            st[v] += st[x];
            st[x].clear();
        }
        st[v].addAbsoluteXA(C[v]);
    }};
    dfs(dfs, 0);
    std::cout << st[0].min() << '\n';
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/Manual/utpc2012_12.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * 東京大学プログラミングコンテスト2012-L じょうしょうツリー
 * https://atcoder.jp/contests/utpc2012/submissions/52989718
 */

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Utility/SlopeTrick.hpp"

#include <queue>
#include <optional>
#include <type_traits>
#include <vector>

namespace zawa {

    // domain, codomain
    template <class D, class C>
    class SlopeTrick {
        static_assert(std::is_integral_v<D>, "zawa::SlopeTrick::D must be integral");
        static_assert(std::is_integral_v<C>, "zawa::SlopeTrick::C must be integral");
    public:
        using SizeType = usize;
        SlopeTrick() = default;
        SlopeTrick(const SlopeTrick& st) : L_{st.L_}, R_{st.R_}, min_{st.min_} {}
        SlopeTrick(SlopeTrick&& st) : L_{std::move(st.L_)}, R_{std::move(st.R_)}, min_{st.min_} {}
        SlopeTrick& operator=(const SlopeTrick& st) {
            L_ = st.L_;
            R_ = st.R_;
            min_ = st.min_;
            return *this;
        }
        SlopeTrick& operator=(SlopeTrick&& st) {
            L_ = std::move(st.L_);
            R_ = std::move(st.R_);
            min_ = st.min_;
            return *this;
        }
        // get min
        C min() const {
            return min_;
        }
        // get [l0, r0]
        std::pair<std::optional<D>, std::optional<D>> argmin() const {
            return {
                L_.empty() ? std::nullopt : std::optional<D>{lvalue(L_.top())},
                R_.empty() ? std::nullopt : std::optional<D>{rvalue(R_.top())}
            };
        }
        // add y = c
        void addConstant(C c) {
            min_ += c;
        }
        // add y = max(0, x - a)
        void addMax0XA(D a) {
            if (L_.empty() or lvalue(L_.top()) <= a) {
                pushR(a);
            }
            else {
                pushR(lvalue(L_.top()));
                min_ += lvalue(L_.top()) - a;
                L_.pop();
                pushL(a);
            }
        }
        // add y = max(0, a - x)
        void addMax0AX(D a) {
            if (R_.empty() or a <= rvalue(R_.top())) {
                pushL(a);
            }
            else {
                pushL(rvalue(R_.top()));
                min_ += a - rvalue(R_.top());
                R_.pop();
                pushR(a);
            }
        }
        // add y = |x - a|
        void addAbsoluteXA(D a) {
            addMax0XA(a);
            addMax0AX(a);
        }
        // 前から累積minをとった関数に置き換える
        void prefixMin() {
            R_ = std::move(decltype(R_){});
            addR_ = D{0};
        }
        // 後ろから累積minをとった関数に置き換える
        void suffixMin() {
            L_ = std::move(decltype(L_){});
            addL_ = D{0};
        }
        // g(x) = min f(k) (x - a <= k <= x - b)に置き換える
        void slidingWindowMin(D a, D b) {
            addR_ += b;
            addL_ += a;
        }
        // x軸方向にc平行移動する
        void translation(D c) {
            slidingWindowMin(c, c);
        }
        // 傾きがk -> k + 1 (x < 0)となる点を列挙する
        std::vector<D> enumerateL() const {
            decltype(L_) L{L_};
            std::vector<D> res;
            while (L.size()) {
                res.emplace_back(lvalue(L.top()));
                L.pop();
            }
            return res;
        }
        // 傾きがk -> k + 1 (x >= 0)となる点を列挙する
        std::vector<D> enumerateR() const {
            decltype(R_) R{R_};
            std::vector<D> res;
            while (R.size()) {
                res.emplace_back(rvalue(R.top()));
                R.pop();
            }
            return res;
        }
        // get f(x)
        // 注意: O(N\log N)かかる
        C f(D x) const {
            C res{min_};
            for (auto l : enumerateL()) {
                res += std::max(D{0}, l - x);
            }
            for (auto r : enumerateR()) {
                res += std::max(D{0}, x - r);
            }
            return res;
        }
        void clear() {
            L_ = decltype(L_){};
            R_ = decltype(R_){};
            min_ = D{0};
        }
        SlopeTrick& operator+=(const SlopeTrick& st) {
            min_ += st.min();
            for (auto l : st.enumerateL()) {
                addMax0AX(l);
            }
            for (auto r : st.enumerateR()) {
                addMax0XA(r);
            }
            return *this;
        }
        inline SizeType sizeL() const {
            return L_.size();
        }
        inline SizeType sizeR() const {
            return R_.size();
        }
        inline SizeType size() const {
            return sizeL() + sizeR();
        }
    private:
        std::priority_queue<D> L_{};
        std::priority_queue<D, std::vector<D>, std::greater<D>> R_{};
        D addL_{}, addR_{};
        C min_{};

        inline D lvalue(D l) const noexcept {
            return l + addL_;
        }
        inline D rvalue(D r) const noexcept {
            return r + addR_;
        }
        inline void pushL(D v) noexcept {
            L_.push(v - addL_);
        }
        inline void pushR(D v) noexcept {
            R_.push(v - addR_);
        }
    };

} // namespace zawa
#line 10 "Test/Manual/utpc2012_12.test.cpp"

#line 13 "Test/Manual/utpc2012_12.test.cpp"

using namespace zawa;

void solve() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> C(N), depth(N);
    std::cin >> C[0];
    std::vector<std::vector<int>> g(N);
    for (int i{1} ; i < N ; i++) {
        int P;
        std::cin >> P >> C[i];
        P--;
        g[P].push_back(i);
        depth[i] = depth[P] + 1;
        C[i] += depth[i];
    }
    std::vector<SlopeTrick<int, long long>> st(N);
    auto dfs{[&](auto dfs, int v) -> void {
        for (auto x : g[v]) {
            dfs(dfs, x);
            st[x].prefixMin();
            if (st[v].size() < st[x].size()) {
                std::swap(st[v], st[x]);
            }
            st[v] += st[x];
            st[x].clear();
        }
        st[v].addAbsoluteXA(C[v]);
    }};
    dfs(dfs, 0);
    std::cout << st[0].min() << '\n';
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page