Submission #471778

#	Time	Username	Problem	Language	Result	Execution time	Memory
471778		dutinmeow	Harbingers (CEOI09_harbingers)	C++17	0 / 100	175 ms	65540 KiB

harbingers

#pragma region template

#ifndef __cplusplus
#   error C++ compiler required
#endif

// to override stl features
#define assert _assert 

#ifdef __has_include
#   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/numeric>
#       include <ext/functional>
#       include <ext/rb_tree>
#       include <ext/rope>
        using namespace __gnu_pbds;
        using namespace __gnu_cxx;
#   endif
#else
#   include <bits/stdc++.h>
#endif

#undef assert

#ifndef _GLIBCXX_NO_ASSERT
    void dassert(int line, bool b, std::string err = "") { 
        if (!b)
            std::cerr << "Assertion Failed on line " << line << " : " << err << '\n'; 
    }
#   define assert(...) dassert(__LINE__, __VA_ARGS__) 
#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
#define TFF(x) get<0>(x)
#define TSS(x) get<1>(x)
#define TTT(x) get<2>(x)
#define TQQ(x) get<3>(x)

const ll INF = 2000000011;
const ll llINF = 1e17 + 11;

/** A custom randomized hash function
 *  Verified: N/A */
struct custom_hash { 
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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)(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)(tuple{get<1>(x), get<2>(x), get<3>(x)}));
    }
};

#ifdef PB_DS_ASSOC_CNTNR_HPP
    template<class K, class V> 
    using fast_map = gp_hash_table<K, V, custom_hash>;

    template<class K> 
    using fast_set = fast_map<K, null_type>;
#else 
    template<class K, class V>
    using fast_map = unordered_map<K, V, custom_hash>;

    template<class K>
    using fast_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>; 
#else 
    template<class K, class V>
    using ordered_map = map<K, V>;

    template<class K>
    using ordered_set = set<K>;
#endif

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>
    decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
    }
}

using namespace std;

#pragma endregion Template
using namespace std;

/**
 * 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
 */ 
template<typename T = int64_t>
struct PersistantLiChao {
    struct Line {
        T m, b;
        Line(T _m = 0, T _b = -numeric_limits<T>::min()) : m(_m), b(_b) {}
        T operator()(T x) { return m * x + b; }
        friend ostream& operator<<(ostream &os, const Line &l) { return os << l.m << "x + " << l.b; }
        ~Line() {}
    };

    struct Node {
        Line line;
        Node *left = nullptr, *right = nullptr;
        Node(Node *_left, Node *_right) : left(_left), right(_right) {}
        Node(Line _line = Line(), Node *_left = nullptr, Node *_right = nullptr) : line(_line), left(_left), right(_right) {}
        ~Node() { 
            if (left != nullptr)
                delete left;
            if (right != nullptr)
                delete right;
        }
    };

    vector<Node*> roots;

private:
    T x_min, x_max;

    Node* add(Node *root, Line line, T l, T r) {
        if (!root)
            return new Node(line);
        T root_l = root->line(l), root_r = root->line(r);
        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 new Node(line, root->left, root->right);
        
        T m = (l + r) / 2;
        T root_m = root->line(m), line_m = line(m);
        if (root_m > line_m) {
            if (line_l >= root_l)
                return new Node(root->line, add(root->left, line, l, m), root->right);
            else 
                return new Node(root->line, root->left, add(root->right, line, m + 1, r));
        } else {
            if (root_l >= line_l)
                return new Node(line, add(root->left, root->line, l, m), root->right);
            else 
                return new Node(line, root->left, add(root->right, root->line, m + 1, r));
        }
    }

    T query(Node *root, T x, T l, T r) {
        if (!root)
            return numeric_limits<T>::min();
        if (l == r)
            return root->line(x);
        
        T m = (l + r) / 2;
        if (x <= m)
            return max(root->line(x), query(root->left, x, l, m));
        else 
            return max(root->line(x), query(root->right, x, m + 1, r));
    }

public:
    PersistantLiChao(int _N, T _x_min, T _x_max) : x_min(_x_min), x_max(_x_max) {
        roots.resize(_N, nullptr);
    }

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

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

    int copy(int r) {
        roots.push_back(new Node(*roots[r]));
        return roots.size() - 1;
    }

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

    ~PersistantLiChao() {
        for (auto root : roots)
            delete root;
    }
};

ll N, S[100005], V[100005], dp[100005];
vector<pll> T[100005];
PersistantLiChao<ll> 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);
        }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for (int i = 1; i < N; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        T[u].EB(v, w);
        T[v].EB(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:1: warning: ignoring '#pragma region template' [-Wunknown-pragmas]
    1 | #pragma region template
      | 
harbingers.cpp:184: warning: ignoring '#pragma endregion Template' [-Wunknown-pragmas]
  184 | #pragma endregion Template
      |

• Subtask 1: 0 / 100