Submission #476559

#	Time	Username	Problem	Language	Result	Execution time	Memory
476559		dutinmeow	Harbingers (CEOI09_harbingers)	C++17	30 / 100	147 ms	65540 KiB

harbingers

//#define _GLIBCXX_DEBUG
#pragma region Template
// to override stl features
#define assert _assert
#define unordered_set _unordered_set
#define unordered_map _unordered_map
#if __has_include(<bits/stdc++.h>)
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <initializer_list>
#include <random>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#endif
#if __has_include(<bits/extc++.h>)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/algorithm>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#endif
#undef assert
#undef unordered_set
#undef unordered_map
#ifdef _GLIBCXX_DEBUG
#ifndef _GLIBCXX_NO_ASSERT
inline void _dassert(std::string name, bool b, int line) { if (!b) std::cerr << "Assertion Failed on line " << line << " : (" << name << ") evaluates to false\n"; }
#define assert(b) _dassert(#b, b, __LINE__)
#else
#define assert(...) ;
#endif
#define dbg(args...)                               \
    {                                              \
        std::string _dbg_s = (#args);              \
        std::stringstream _dbg_ss(_dbg_s);         \
        vector<std::string> _dbg_v;                \
        std::string _dbg_x;                        \
        while (std::getline(_dbg_ss, _dbg_x, ',')) \
            _dbg_v.emplace_back(_dbg_x);           \
        _ddbg(_dbg_v.begin(), args);               \
    }
inline void _ddbg(std::vector<std::string>::iterator) {}
template <typename T, typename... Args> inline void _ddbg(std::vector<std::string>::iterator it, T a, Args... args) { std::cerr << it->substr((*it)[0] == ' ') << " = " << a << '\n'; _ddbg(++it, args...); }
#else
#define assert(...)
#define dbg(...)
#endif
#if __cplusplus >= 201703L
namespace std {
    template <class Fun> class y_combinator_result {
        Fun fun_;
    public:
        template <class T> explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
        template <class... Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
    };
    template <class Fun> inline decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
}
#endif
using namespace std;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;
using qii = tuple<int, int, int, int>;
using ll = long long;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using qll = tuple<ll, ll, ll, ll>;
using ld = long double;
using pld = pair<ld, ld>;
using tld = tuple<ld, ld, ld>;
using qld = tuple<ld, ld, ld, ld>;
#define FF first
#define SS second
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define PPB pop_back
#define PPF pp_front
const ll INF = 2000000011, llINF = 1e17 + 11;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
    size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); }
    size_t operator()(pair<uint64_t, uint64_t> x) const { return (*this)(x.first) ^ __builtin_bswap64((*this)(x.second)); }
    size_t operator()(tuple<uint64_t, uint64_t, uint64_t> x) const { return (*this)(get<0>(x)) + __builtin_bswap64((*this)(make_pair(get<1>(x), get<2>(x)))); }
    size_t operator()(tuple<uint64_t, uint64_t, uint64_t, uint64_t> x) const { return (*this)(get<0>(x)) + __builtin_bswap64((*this)(make_tuple(get<1>(x), get<2>(x), get<3>(x)))); }
};
#ifdef PB_DS_ASSOC_CNTNR_HPP
template <class K, class V> using unordered_map = gp_hash_table<K, V, custom_hash>;
template <class K> using unordered_set = gp_hash_table<K, null_type, custom_hash>;
#else
template <class K, class V> using map = _unordered_map<K, V, custom_hash>;
template <class K> using set = _unordered_set<K, custom_hash>;
#endif
#ifdef PB_DS_TREE_POLICY_HPP
template <class K, class V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K> using ordered_set = ordered_map<K, null_type>;
#endif
#pragma endregion Template

/**
 * A Persistant Li Chao Impelementation
 * Useful for Convex Hull Trick on Trees
 * Complexity: O(log C)
 * Verified: https://judge.yosupo.jp/problem/line_add_get_min
 */ 
struct PersistantLiChao {
    struct Line {
        int64_t m, b;
        Line(int64_t _m = 0, int64_t _b = numeric_limits<int64_t>::min()) : m(_m), b(_b) {}
        int64_t operator()(int64_t x) { return m * x + b; }
        friend ostream& operator<<(ostream &os, const Line &l) { return os << l.m << "x + " << l.b; }
        ~Line() {}
    };

    struct Node {
        int id;
        Line line;
        size_t left = -1, right = -1;
        Node(size_t _left, size_t _right) : left(_left), right(_right) {}
        Node(int _id, Line _line = Line(), size_t _left = -1, size_t _right = -1) : id(_id), line(_line), left(_left), right(_right) {}
    };

    vector<int> roots;
    vector<Node> nodes;

private:
    int64_t x_min, x_max;

    int node(int id, Line line, int left = -1, int right = -1) { 
        nodes.emplace_back(id, line, left, right);
        return nodes.size() - 1;
    }

    int add(int id, int root, Line line, int64_t l, int64_t r) {
        if (root == -1)
            return node(id, line);
        int64_t root_l = nodes[root].line(l), root_r = nodes[root].line(r);
        int64_t line_l = line(l), line_r = line(r);

        if (root_l >= line_l && root_r >= line_r)
            return root;
        if (root_l <= line_l && root_r <= line_r) 
            return node(id, line, nodes[root].left, nodes[root].right);
        
        int64_t m = (l + r) / 2;
        int64_t root_m = nodes[root].line(m), line_m = line(m);
        if (root_m > line_m) {
            if (line_l >= root_l)
                return node(id, nodes[root].line, add(id, nodes[root].left, line, l, m), nodes[root].right);
            else 
                return node(id, nodes[root].line, nodes[root].left, add(id, nodes[root].right, line, m + 1, r));
        } else {
            if (root_l >= line_l)
                return node(id, line, add(id, nodes[root].left, nodes[root].line, l, m), nodes[root].right);
            else 
                return node(id, line, nodes[root].left, add(id, nodes[root].right, nodes[root].line, m + 1, r));
        }
    }

    int64_t query(int root, int64_t x, int64_t l, int64_t r) {
        if (root == -1)
            return numeric_limits<int64_t>::min();
        if (l == r)
            return nodes[root].line(x);
        
        int64_t m = (l + r) / 2;
        if (x <= m)
            return max(nodes[root].line(x), query(nodes[root].left, x, l, m));
        else 
            return max(nodes[root].line(x), query(nodes[root].right, x, m + 1, r));
    }

public:
    PersistantLiChao(int N, int64_t _x_min, int64_t _x_max) : x_min(_x_min), x_max(_x_max) {
        roots.resize(N, -1);
    }

    void add(int r, const int64_t &m, const int64_t &b) {
        Line line(m, b);
        roots[r] = (add(r, roots[r], line, x_min, x_max));
    }

    int64_t query(int r, int64_t x) {
        return query(roots[r], x, x_min, x_max);
    }

    int copy(int r) {
        roots.emplace_back(roots[r]);
        return roots.size() - 1;
    }

    int copy(int r1, int r2) {
        roots[r2] = roots[r1];
        return r2;
    }

    void destroy(int id) {
        //int cnt = 0;
        while (!nodes.empty() && nodes[nodes.size() - 1].id == id) {
            nodes.PPB();
            //cnt++;
        }
        //return cnt;
    }

    ~PersistantLiChao() {}
};

ll N, S[100005], V[100005], dp[100005];
vector<pll> T[100005];
PersistantLiChao plc(100005, 0, 1e9);

void dfs(int u, int p, ll pre) {
    if (u == 1) {
        dp[u] = 0;
        plc.add(u, 0, 0);
    }
    else {
        dp[u] = -plc.query(u, V[u]) + S[u] + pre * V[u];
        plc.add(u, pre, -dp[u]);
    }
    for (auto [v, w] : T[u])
        if (v != p) {
            plc.copy(u, v);
            dfs(v, u, pre + w);
        }
    plc.destroy(u);
}

int main() {
#ifndef _GLIBCXX_DEBUG
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif
    plc.nodes.reserve(1000005);

    cin >> N;
    for (int i = 1; i < N; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        T[u].emplace_back(v, w);
        T[v].emplace_back(u, w);
    }
    for (int i = 2; i <= N; i++)
        cin >> S[i] >> V[i];
    
    dfs(1, 0, 0);

    for (int i = 2; i <= N; i++)
        cout << dp[i] << ' ';
    cout << '\n';
}

Compilation message (stderr)

harbingers.cpp:2: warning: ignoring '#pragma region Template' [-Wunknown-pragmas]
    2 | #pragma region Template
      | 
harbingers.cpp:128: warning: ignoring '#pragma endregion Template' [-Wunknown-pragmas]
  128 | #pragma endregion Template
      |

• Subtask 1: 30 / 100