#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 7;
int n, m, x[maxn], y[maxn], cnt, v[maxn], d[maxn], st[maxn], ahihi, l, r, ans;
int mid;
int a[maxn], dp[maxn];
vector<pair<int, int>> vt[maxn];
struct Line
{
int id;
int a, b;
Line(){}
Line(int id, int a, int b): id(id), a(a), b(b) {};
};
int Get(const Line & u, const int &v)
{
return u.a * v + u.b;
}
bool Ok(const Line &u, const Line &v, const Line &w)
{
return (u.b - v.b) * (w.a - u.a) < (u.b - w.b) * (v.a - u.a);
}
vector<pair<int, Line>> deleted;
vector<Line> hull;
void Insert(int u, Line x)
{
while(hull.size() > 1 && !Ok(hull[hull.size() - 2], hull[hull.size() - 1], x))
{
ahihi++;
deleted.push_back({u, hull.back()});
hull.pop_back();
}
hull.push_back(x);
}
int Find(const int &x)
{
l = 0;
r = hull.size() - 1;
while(l <= r)
{
ahihi++;
mid = l + r >> 1;
if(mid == hull.size() - 1) l = mid + 1;
else if(Get(hull[mid], x) > Get(hull[mid + 1], x)) l = mid + 1;
else r = mid - 1;
}
ans = LLONG_MAX;
if(r >= 0 && r <= hull.size() - 1) ans = min(ans, Get(hull[r], x));
if(l >= 0 && l <= hull.size() - 1) ans = min(ans, Get(hull[l], x));
return ans;
}
void DFS(int u, int p)
{
st[u] = ++cnt;
if(u != 1) dp[u] = a[u] + d[u] * v[u] + Find(v[u]);
Insert(cnt, Line(cnt, -d[u], dp[u]));
for(auto i: vt[u])
{
int v = i.first;
int w = i.second;
if(v != p)
{
d[v] = d[u] + w;
DFS(v, u);
while(hull.size() && hull.back().id > st[u])
{
ahihi++;
hull.pop_back();
}
int cac = -1;
for(int j = (int)deleted.size() - 1; j >= 0; j--)
{
if(deleted[j].first == st[v])
{
ahihi++;
hull.push_back(deleted[j].second);
deleted.pop_back();
}
else break;
}
}
}
hull.pop_back();
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
vt[u].push_back({v, w});
vt[v].push_back({u, w});
}
for(int i = 2; i <= n; i++) cin >> a[i] >> v[i];
DFS(1, 1);
for(int i = 2; i <= n; i++) cout << dp[i] << ' ';
}
Compilation message
harbingers.cpp: In function 'long long int Find(const long long int&)':
harbingers.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = l + r >> 1;
~~^~~
harbingers.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mid == hull.size() - 1) l = mid + 1;
~~~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(r >= 0 && r <= hull.size() - 1) ans = min(ans, Get(hull[r], x));
~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l >= 0 && l <= hull.size() - 1) ans = min(ans, Get(hull[l], x));
~~^~~~~~~~~~~~~~~~~~
harbingers.cpp: In function 'void DFS(long long int, long long int)':
harbingers.cpp:78:17: warning: unused variable 'cac' [-Wunused-variable]
int cac = -1;
^~~
harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:98:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:98:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5116 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5880 KB |
Output is correct |
| 3 |
Correct |
72 ms |
16020 KB |
Output is correct |
| 4 |
Correct |
99 ms |
21068 KB |
Output is correct |
| 5 |
Correct |
143 ms |
25656 KB |
Output is correct |
| 6 |
Correct |
184 ms |
30232 KB |
Output is correct |
| 7 |
Correct |
93 ms |
17132 KB |
Output is correct |
| 8 |
Execution timed out |
1053 ms |
24424 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1065 ms |
19724 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1078 ms |
24808 KB |
Time limit exceeded |
