#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const ll oo = 1e18;
int n, s[nmax], v[nmax];
vector <pii> adj[nmax];
ll dist[nmax], dp[nmax];
struct segment
{
ll a, b;
segment(ll a = 0, ll b = 0) : a(a), b(b) {}
} lst[nmax];
int m = 0;
struct persistent
{
int id, old_m;
segment old_line;
persistent(int id, int old_m, const segment& old_line): id(id), old_m(old_m), old_line(old_line) {}
};
stack <persistent> st;
double intersect(const segment &x, const segment &y)
{
return 1.0 * (y.b - x.b) / (x.a - y.a);
}
void add(const segment &x)
{
int l = 2, r = m, ans = m + 1;
while(l <= r)
{
int mid = l + r >> 1;
if (intersect(lst[mid - 1], x) <= intersect(lst[mid - 1], lst[mid]))
ans = mid, r = mid - 1;
else l = mid + 1;
}
st.emplace(ans, m, lst[ans]);
m = ans;
lst[m] = x;
}
void undo()
{
auto [id, old_m, old_line] = st.top();
st.pop();
m = old_m;
lst[id] = old_line;
}
ll get(int x)
{
int l = 2, r = m, ans = 1;
while(l <= r)
{
int mid = l + r >> 1;
if (intersect(lst[mid - 1], lst[mid]) <= x)
ans = mid, l = mid + 1;
else r = mid - 1;
}
return 1ll * lst[ans].a * x + lst[ans].b;
}
void dfs(int u, int par = -1)
{
if (u != 1)
dp[u] = get(v[u]) + 1ll * dist[u] * v[u] + s[u];
add({-dist[u], dp[u]});
for (auto &[w, v] : adj[u])
{
if (v == par) continue;
dist[v] = dist[u] + w;
dfs(v, u);
}
undo();
}
int main()
{
if (ifstream(task".inp")) nx
fast
cin >> n;
for (int u, v, w, i = 1; i < n; ++i)
{
cin >> u >> v >> w;
adj[u].eb(w, v);
adj[v].eb(w, u);
}
for (int i = 2; i <= n; ++i)
cin >> s[i] >> v[i];
dfs(1);
for (int i = 2; i <= n; ++i)
cout << dp[i] << ' ';
}
Compilation message
harbingers.cpp: In function 'void add(const segment&)':
harbingers.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'long long int get(int)':
harbingers.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:83:31: note: in expansion of macro 'nx'
83 | if (ifstream(task".inp")) nx
| ^~
harbingers.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:83:31: note: in expansion of macro 'nx'
83 | if (ifstream(task".inp")) nx
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6308 KB |
Output is correct |
| 3 |
Correct |
32 ms |
14156 KB |
Output is correct |
| 4 |
Correct |
41 ms |
17628 KB |
Output is correct |
| 5 |
Correct |
51 ms |
21352 KB |
Output is correct |
| 6 |
Correct |
66 ms |
24812 KB |
Output is correct |
| 7 |
Correct |
45 ms |
14192 KB |
Output is correct |
| 8 |
Correct |
97 ms |
18504 KB |
Output is correct |
| 9 |
Correct |
72 ms |
20816 KB |
Output is correct |
| 10 |
Correct |
67 ms |
19264 KB |
Output is correct |
