제출 #476559

#제출 시각아이디문제언어결과실행 시간메모리
476559dutinmeowHarbingers (CEOI09_harbingers)C++17
30 / 100
147 ms65540 KiB
//#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'; }

컴파일 시 표준 에러 (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
      |
#Verdict Execution timeMemoryGrader output
Fetching results...