#include <cstdio>
#include <stack>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)
#define N 200005
#define ALL(x) x.begin(), x.end()
struct line
{
ll m, c;
line(ll m, ll c) : m(m), c(c) {}
ll operator[](ll x) { return m*x+c; }
ll intersect(line &l) { return (ld)(c-l.c)/(l.m-m); }
};
ostream& operator<<(ostream &out, line k)
{
out << '{'<<k.m << ", " <<k.c<<'}';
return out;
}
int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];
struct cht_rollback : deque<line>
{
stack<tuple<int, line>> saves;
stack<int> at;
void pop_back_save()
{
saves.emplace(0, back());
pop_back();
}
void push_back_save(line k)
{
saves.emplace(1, k);
push_back(k);
}
void rollback()
{
while (saves.size() > at.top())
{
auto [t, k] = saves.top(); saves.pop();
if (t) pop_back();
else push_back(k);
}
at.pop();
}
void add(line k)
{
at.push(saves.size());
while (size() > 1)
{
if ((back().m == k.m && back().c <= k.c) ||
back().intersect((*this)[size()-2]) > back().intersect(k)) pop_back_save();
else break;
}
if (size() && back().m == k.m && back().c >= k.c) return;
push_back_save(k);
}
ll qry(ll x)
{
if (empty()) return 0;
int l = 0, r = size() - 2, z = size() - 1;
for (;l <= r;)
{
int m = (l+r)/2;
if ((*this)[m].intersect((*this)[m+1]) < x) l=m+1;
else r=m-1, z = m;
}
return (*this)[z][x];
}
};
cht_rollback cht;
void dfs(int u, int p)
{
//cerr << "E " << u << ' ' << cht.size(); for (auto x : cht) cout << x<<' '; cout<<endl;
dp[u] = s[u] + 1ll*v[u]*rt[u] - cht.qry(v[u]);
dp[1] = 0;
cht.add(line{rt[u], -dp[u]});
for (auto [w, v] : g[u]) if (v != p)
{
rt[v] = rt[u] + w;
dfs(v, u);
}
cht.rollback();
}
int main()
{
ShinLena;
cin >> n;
for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
dfs(1, 1);
for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';
return 0;
}
Compilation message
harbingers.cpp: In member function 'void cht_rollback::rollback()':
harbingers.cpp:59:29: warning: comparison of integer expressions of different signedness: 'std::stack<std::tuple<int, line> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
59 | while (saves.size() > at.top())
| ~~~~~~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8796 KB |
Output is correct |
2 |
Correct |
3 ms |
9360 KB |
Output is correct |
3 |
Correct |
39 ms |
17216 KB |
Output is correct |
4 |
Correct |
50 ms |
21076 KB |
Output is correct |
5 |
Correct |
59 ms |
25224 KB |
Output is correct |
6 |
Correct |
91 ms |
29520 KB |
Output is correct |
7 |
Correct |
46 ms |
15884 KB |
Output is correct |
8 |
Execution timed out |
1054 ms |
19048 KB |
Time limit exceeded |
9 |
Execution timed out |
1027 ms |
15896 KB |
Time limit exceeded |
10 |
Execution timed out |
1062 ms |
20880 KB |
Time limit exceeded |