//#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
struct Line {
ll m, b;
Line(ll _m = 0, ll _b = 0) : m(_m), b(_b) {}
ll operator()(ll x) { return m * x + b; }
friend ld intersect(Line l1, Line l2) { return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m); }
friend ostream& operator<<(ostream &os, const Line &l) { return os << l.m << "x + " << l.b; }
~Line() {}
};
int N;
ll S[100005], V[100005], dp[100005];
vector<pll> T[100005];
Line stk[100005];
int stk_max = 0;
ll line_min(ll x) {
int l = 0, r = stk_max - 1;
while (l < r) {
int m = (l + r) / 2;
if (intersect(stk[m], stk[m + 1]) < x)
l = m + 1;
else
r = m;
}
return stk[l](x);
}
// first pos where intersect(line, stk[pos]) < intersect(stj[pos], stk[pos - 1])
// if no position then returns -1 --> append new line
// assume that line has lesser slope than any previous line
ll remove_pos(Line line) {
if (stk_max < 2 || intersect(line, stk[stk_max - 1]) >= intersect(stk[stk_max - 1], stk[stk_max - 2]))
return stk_max;
int l = 1, r = stk_max - 1;
while (l < r) {
int m = (l + r) / 2;
if (intersect(line, stk[m]) < intersect(stk[m], stk[m - 1]))
r = m;
else
l = m + 1;
}
return l;
}
void dfs(int u = 1, int p = 0, ll d = 0) {
int prev_max, prev_pos;
Line prev_line;
if (u == 1) {
dp[u] = 0;
stk[stk_max++] = {0, 0};
} else {
dp[u] = line_min(V[u]) + d * V[u] + S[u];
Line l(-d, dp[u]);
prev_max = stk_max;
prev_pos = stk_max = remove_pos(l);
prev_line = stk[stk_max];
stk[stk_max++] = l;
}
for (auto [v, w] : T[u])
if (v != p)
dfs(v, u, d + w);
if (u != 1) {
stk_max = prev_max;
stk[prev_pos] = prev_line;
}
}
int main() {
#ifndef _GLIBCXX_DEBUG
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
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();
for (int i = 2; i <= N; i++)
cout << dp[i] << ' ';
cout << '\n';
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4172 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4888 KB |
Output is correct |
| 3 |
Correct |
53 ms |
14868 KB |
Output is correct |
| 4 |
Correct |
78 ms |
19568 KB |
Output is correct |
| 5 |
Correct |
121 ms |
24472 KB |
Output is correct |
| 6 |
Correct |
140 ms |
29156 KB |
Output is correct |
| 7 |
Correct |
69 ms |
15420 KB |
Output is correct |
| 8 |
Correct |
132 ms |
21164 KB |
Output is correct |
| 9 |
Correct |
171 ms |
23556 KB |
Output is correct |
| 10 |
Correct |
108 ms |
21696 KB |
Output is correct |
