#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7; // !
int t, v[N], s[N], n, cur_sz;
ll dp[N], h[N];
vector<pii> V[N];
struct line {
int k, b;
};
vector<line> ts;
ll f(int k,int x,int b) {
return (ll)k * x + b;
}
double X_(line a, line b) {
// a.k * x + a.b = b.k * x + b.b
return (double)(b.b - a.b) / (a.k - b.k);
}
void dfs(int u,int p) {
// s[u] + (h[u] - h[p]) * v[u] + dp[p]
// -h[p] * v[u] + dp[p] + s[u] + h[u] * v[u]
vector<line> rem;
dp[u] = 0;
int l = 0, r = cur_sz - 2;
if(cur_sz) dp[u] = min(dp[u], f(ts[0].k, v[u], ts[0].b));
// cout << endl;
// for(int j = 0; j < cur_sz; j++) cout << ts[j].k<<" " << ts[j].b << endl;
// cout << endl;
while(l <= r) {
int mid = (l + r) / 2;
if(X_(ts[mid], ts[mid + 1]) <= v[u]) l = mid + 1, dp[u] = min(dp[u], f(ts[mid + 1].k, v[u], ts[mid + 1].b));
else r = mid - 1;
}
dp[u] += (ll) h[u] * v[u] + s[u];
line new_;
new_.k = -h[u]; new_.b = dp[u];
l = 0, r = cur_sz - 2;
int pos = cur_sz;
while(l <= r) {
int mid = (l + r) / 2;
if(X_(ts[mid], ts[mid + 1]) >= X_(ts[mid + 1], new_)) pos = mid + 1, r = mid - 1;
else l = mid + 1;
}
int prev_sz = cur_sz;
line prev_val = {0, 0};
if(pos == cur_sz) cur_sz++, ts.push_back(new_);
else prev_val = ts[pos], ts[pos] = new_, cur_sz = pos + 1;
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i].f == p) continue;
h[V[u][i].f] = h[u] + V[u][i].s;
dfs(V[u][i].f, u);
}
if(prev_sz == cur_sz - 1) ts.pop_back(), cur_sz--;
else ts[pos] = prev_val, cur_sz = prev_sz;
}
main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n; cin >> n;
for(int i = 2; i <= n; i++) {
int u,v, w;
cin >> u >> v >> w;
V[u].push_back({v, w});
V[v].push_back({u, w});
}
for(int i = 2; i <= n; i++) {
int p;
cin >> s[i] >> v[i];
}
dfs(1, 0);
for(int i = 2; i <= n; i++) cout << dp[i] <<" ";
}
Compilation message
harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
harbingers.cpp: At global scope:
harbingers.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
60 | main(){
| ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:70:7: warning: unused variable 'p' [-Wunused-variable]
70 | int p;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
3068 KB |
Output isn't correct |
| 3 |
Incorrect |
31 ms |
10052 KB |
Output isn't correct |
| 4 |
Incorrect |
53 ms |
13664 KB |
Output isn't correct |
| 5 |
Incorrect |
65 ms |
17348 KB |
Output isn't correct |
| 6 |
Incorrect |
87 ms |
20724 KB |
Output isn't correct |
| 7 |
Incorrect |
50 ms |
10688 KB |
Output isn't correct |
| 8 |
Incorrect |
82 ms |
13988 KB |
Output isn't correct |
| 9 |
Incorrect |
94 ms |
16316 KB |
Output isn't correct |
| 10 |
Incorrect |
70 ms |
15552 KB |
Output isn't correct |
