//ya prep
#ifndef DBG
#define NDEBUG
#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#endif // DBG
#define _GLIBCXX_FILESYSTEM
#include <bits/stdc++.h>
using namespace std;
#define cn const
#define cauto cn auto
#define FOR(i, from, to) for (int i = (from); i <= int(to); ++i)
#define FORN(i, n) FOR(i, 0, (n) - 1)
#define endl '\n'
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define X F
#define Y S
#define CONT(c) begin(c), end(c)
#define ARR(a, sz) (a), ((a) + (sz))
using ll = long long;
using ull = unsigned long long;
using ulong = unsigned long;
using uint = unsigned;
//#undef DBG
#ifdef DBG
cn bool dbg = true;
#else
cn bool dbg = false;
#endif // DBG
#ifdef MY
cn bool my = true;
#else
cn bool my = false;
#endif // MY
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<typename Key>
using ordered_set = __gnu_pbds::tree<Key, __gnu_pbds::null_type, less<Key>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename Key, typename Value>
using ordered_map = __gnu_pbds::tree<Key, Value, less<Key>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename T>
constexpr T sqr(const T& x)
{
return x * x;
}
template<typename T>
bool rMin(T& v, const T& rval)
{
if (rval < v) {
v = rval;
return true;
}
return false;
}
template<typename T>
bool rMax(T& v, const T& rval)
{
if (v < rval) {
v = rval;
return true;
}
return false;
}
ll rd()
{
ll x;
cin >> x;
assert(cin);
return x;
}
/*
template<int Modulo>
struct MOD {
static cn int M = Modulo;
uint x;
constexpr MOD(int val = 0) : x(val) { assert(0 <= val && val < M); }
constexpr MOD& operator +=(MOD r) {
x += r.x;
if (x >= M)
x -= M;
return *this;
}
friend constexpr MOD operator +(MOD l, MOD r) { return l += r; }
constexpr MOD& operator *=(MOD r) {
x = (ll(x) * r.x) % M;
return *this;
}
friend constexpr MOD operator *(MOD l, MOD r) { return l *= r; }
constexpr MOD& operator -=(MOD r) {
x -= r.x;
if (x >= M)
x += M;
return *this;
}
friend constexpr MOD operator -(MOD l, MOD r) { return l -= r; }
friend constexpr MOD operator -(MOD a) {
if (a.x)
return M - a.x;
return 0;
}
friend ostream& operator <<(ostream& cout, MOD x) { return cout << x.x; }
friend constexpr bool operator ==(MOD l, MOD r) { return l.x == r.x; }
friend constexpr bool operator <(MOD l, MOD r) { return l.x < r.x; }
};
namespace std {
template<int Modulo>
struct hash<MOD<Modulo>> {
size_t operator ()(MOD<Modulo> a) const noexcept { return a.x; }
};
}
using Mersen32Mod = MOD<(1LL << 31) - 1>;
template<>
Mersen32Mod& Mersen32Mod::operator *=(Mersen32Mod r) {
cauto mul = ll(x) * r.x;
x = (mul >> 31) + (mul & M);
if (x >= M)
x -= M;
return *this;
}
template<int M>
constexpr MOD<M> binpow(MOD<M> a, ll p)
{
MOD<M> res = 1;
while (p != 0) {
if (p % 2)
res *= a;
a *= a;
p /= 2;
}
return res;
}
*/
/*
struct DoubleHash {
uint r1;
Mersen32Mod r2;
DoubleHash(int x = 0) {
r1 = x;
r2 = x;
}
DoubleHash(initializer_list<int> lst) {
assert(lst.size() == 2);
auto it = lst.begin();
r1 = *it++;
r2 = *it;
}
DoubleHash& operator +=(DoubleHash R) {
r1 += R.r1;
r2 += R.r2;
return *this;
}
friend DoubleHash operator +(DoubleHash L, DoubleHash R) {
return L += R;
}
DoubleHash& operator -=(DoubleHash R) {
r1 -= R.r1;
r2 -= R.r2;
return *this;
}
friend DoubleHash operator -(DoubleHash L, DoubleHash R) {
return L -= R;
}
DoubleHash& operator *=(DoubleHash R) {
r1 *= R.r1;
r2 *= R.r2;
return *this;
}
friend DoubleHash operator *(DoubleHash L, DoubleHash R) {
return L *= R;
}
friend bool operator ==(DoubleHash L, DoubleHash R) {
return L.r1 == R.r1 && L.r2 == R.r2;
}
friend bool operator <(DoubleHash L, DoubleHash R) {
return mp(L.r1, L.r2) < mp(R.r1, R.r2);
}
size_t hash() const {
return r2.x;
}
};
namespace std {
template<>
struct hash<DoubleHash> {
auto operator ()(DoubleHash h) const noexcept { return h.hash(); }
};
}
*/
//#include "limits.h"
cn int N = 1e5 + 1;
vector<pair<int, int>> g[N];
pair<int, int> courier[N];
int n;
ll dp[N];
vector<int> big;
int compress(int big_x)
{
assert(binary_search(CONT(big), big_x));
return lower_bound(CONT(big), big_x) - begin(big);
}
struct Line {
ll k, b;
ll operator()(int small_x) const {
assert(0 <= small_x && small_x < int(big.size()));
return k * big[small_x] + b;
}
};
cn int R = 1 << 17;
Line t[2 * R];
vector<pair<int, Line>> changes;
int cht_add(Line f)
{
cn int sz = changes.size();
int vl = 0, vr = R;
for (int v = 1; v < 2 * R; ) {
cauto vm = (vl + vr) / 2;
if (vm >= int(big.size())) {
v = 2 * v;
vr = vm;
continue;
}
auto& vf = t[v];
cauto l = vf(vl) < f(vl);
cauto m = vf(vm) < f(vm);
if (!m) {
changes.pb({v, vf});
swap(f, vf);
}
if (l ^ m) {
v = 2 * v;
vr = vm;
} else {
v = 2 * v + 1;
vl = vm;
}
}
return sz;
}
void undo(int sz)
{
for (; int(changes.size()) != sz; changes.pop_back()) {
cauto [v, f] = changes.back();
t[v] = f;
}
}
cn ll INF = 2e18;
ll cht_min(int big_x)
{
cauto small = compress(big_x);
ll res = INF;
for (int v = small + R; v; v >>= 1)
res = min(res, t[v](small));
return res;
}
void dfs(int v, int pr, int h)
{
cauto [start, speed] = courier[v];
dp[v] = ll(h) * speed + cht_min(speed) + start;
cauto sz = cht_add({-h, dp[v]});
for (auto [to, len] : g[v])
if (to != pr)
dfs(to, v, h + len);
undo(sz);
}
int main()
{
#ifdef MY
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#else
#define FILEIO(TASK) do { freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout); } while (false)
//FILEIO("bicycle");
#endif // MY
if (!dbg) {
ios_base::sync_with_stdio(false);
cin.tie(0);
}
cin >> n;
FORN(i, n - 1) {
int u, v, len;
cin >> u >> v >> len;
g[u].pb({v, len});
g[v].pb({u, len});
}
big.pb(0);
FOR(v, 2, n) {
cin >> courier[v].F >> courier[v].S;
big.pb(courier[v].S);
}
sort(CONT(big));
big.resize(unique(CONT(big)) - begin(big));
dfs(1, -1, 0);
FOR(v, 2, n)
cout << dp[v] << " ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3540 KB |
Output is correct |
| 3 |
Correct |
84 ms |
21784 KB |
Output is correct |
| 4 |
Runtime error |
123 ms |
36200 KB |
Memory limit exceeded |
| 5 |
Runtime error |
232 ms |
65428 KB |
Memory limit exceeded |
| 6 |
Correct |
168 ms |
25868 KB |
Output is correct |
| 7 |
Correct |
105 ms |
15144 KB |
Output is correct |
| 8 |
Correct |
210 ms |
24588 KB |
Output is correct |
| 9 |
Runtime error |
204 ms |
39684 KB |
Memory limit exceeded |
| 10 |
Correct |
157 ms |
27692 KB |
Output is correct |
