#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
*/
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 {
Line line;
size_t left = -1, right = -1;
Node(size_t _left, size_t _right) : left(_left), right(_right) {}
Node(Line _line = Line(), size_t _left = -1, size_t _right = -1) : line(_line), left(_left), right(_right) {}
};
vector<int> roots;
vector<Node> nodes;
private:
int64_t x_min, x_max;
int node(Line line, int left = -1, int right = -1) {
nodes.emplace_back(line, left, right);
return nodes.size() - 1;
}
int add(int root, Line line, int64_t l, int64_t r) {
if (root == -1)
return node(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(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(nodes[root].line, add(nodes[root].left, line, l, m), nodes[root].right);
else
return node(nodes[root].line, nodes[root].left, add(nodes[root].right, line, m + 1, r));
} else {
if (root_l >= line_l)
return node(line, add(nodes[root].left, nodes[root].line, l, m), nodes[root].right);
else
return node(line, nodes[root].left, add(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(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;
}
~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);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
plc.nodes.reserve(100005);
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
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
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4172 KB |
Output is correct |
| 3 |
Runtime error |
84 ms |
36532 KB |
Memory limit exceeded |
| 4 |
Runtime error |
151 ms |
65540 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
126 ms |
35024 KB |
Memory limit exceeded |
| 6 |
Runtime error |
147 ms |
36872 KB |
Memory limit exceeded |
| 7 |
Correct |
114 ms |
25388 KB |
Output is correct |
| 8 |
Runtime error |
208 ms |
65536 KB |
Memory limit exceeded |
| 9 |
Runtime error |
195 ms |
65540 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
181 ms |
65536 KB |
Memory limit exceeded |
