#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;
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(int x)
{
int l = 0;
int r = hull.size() - 1;
while(l <= r)
{
int 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;
}
int 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();
}
}
}
}
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] << ' ';
cerr << ahihi;
}
Compilation message
harbingers.cpp: In function 'long long int Find(long long int)':
harbingers.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
harbingers.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mid == hull.size() - 1) l = mid + 1;
~~~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:54: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:55: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:77:17: warning: unused variable 'cac' [-Wunused-variable]
int cac = -1;
^~~
harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:96: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:96:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Incorrect |
12 ms |
5880 KB |
Output isn't correct |
| 3 |
Incorrect |
927 ms |
16132 KB |
Output isn't correct |
| 4 |
Execution timed out |
1071 ms |
20340 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1048 ms |
25072 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1074 ms |
29472 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1075 ms |
17216 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1055 ms |
24552 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1077 ms |
19828 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1077 ms |
25192 KB |
Time limit exceeded |
