#include <bits/stdc++.h>
#define long long long
#define pii pair<long, long>
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
vector<int> coord;
struct item {
pii val;
int l, r;
item() : val(pii(1e9, 1e9)), l(-1), r(-1) {}
item(pii val, int l, int r) : val(val), l(l), r(r) {}
} t[9 * N];
long f(int x, pii l) { return 1ll * l.x * x + l.y; };
int ptr;
int newleaf(pii x) {
t[++ptr].val = x;
t[ptr].l = -1, t[ptr].r = -1;
return ptr;
}
int newpar(pii x, int l, int r) {
t[++ptr].val = x;
t[ptr].l = l, t[ptr].r = r;
return ptr;
}
int add(pii k, int p, int l = 1, int r = coord.size()) {
int m = (l + r) >> 1;
int L = coord[l-1], M = coord[m-1], R = coord[r-1];
if(p == -1) return newleaf(k);
if(f(L, k) <= f(L, t[p].val) && f(R, k) <= f(R, t[p].val)) return newpar(k, t[p].l, t[p].r);
if(f(L, k) >= f(L, t[p].val) && f(R, k) >= f(R, t[p].val)) return p;
bool lef = f(L, k) < f(L, t[p].val);
bool mid = f(M, k) < f(M, t[p].val);
pii ret = t[p].val;
if(mid) swap(ret, k);
if(lef != mid) return newpar(ret, add(k, t[p].l, l, m), t[p].r);
else return newpar(ret, t[p].l, add(k, t[p].r, m + 1, r));
}
long get(int x, int p, int l = 1, int r = coord.size()) {
int m = (l + r) >> 1;
int L = coord[l-1], M = coord[m-1], R = coord[r-1];
if(p == -1) return 1e18;
if(x <= M) return min(f(x, t[p].val), get(x, t[p].l, l, m));
else return min(f(x, t[p].val), get(x, t[p].r, m + 1, r));
}
int n;
vector<pii> g[N];
int S[N], V[N], ver[N];
long ans[N];
void dfs(int u, int p, int d) {
if(u != 1) ans[u] = get(V[u], ver[p]) + 1ll * d * V[u] + S[u];
if(u != 1) ver[u] = add(pii(-d, ans[u]), ver[p]);
else ver[u] = newleaf(pii(0, 0));
for(pii v : g[u]) if(v.x != p) dfs(v.x, u, d + v.y);
}
int main() {
scanf("%d", &n);
for(int i = 1, a, b, c; i < n; i++) {
scanf("%d %d %d", &a, &b, &c);
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
for(int i = 2; i <= n; i++) {
scanf("%d %d", S + i, V + i);
coord.emplace_back(V[i]);
}
sort(coord.begin(), coord.end());
coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
dfs(1, 0, 0);
for(int i = 2; i <= n; i++) printf("%lld ", ans[i]);
printf("\n");
return 0;
}
Compilation message
harbingers.cpp: In function 'long long int get(int, int, int, int)':
harbingers.cpp:54:9: warning: unused variable 'L' [-Wunused-variable]
int L = coord[l-1], M = coord[m-1], R = coord[r-1];
^
harbingers.cpp:54:41: warning: unused variable 'R' [-Wunused-variable]
int L = coord[l-1], M = coord[m-1], R = coord[r-1];
^
harbingers.cpp: In function 'int main()':
harbingers.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
harbingers.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", S + i, V + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
96 ms |
30148 KB |
Output is correct |
| 4 |
Runtime error |
131 ms |
33136 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 5 |
Runtime error |
152 ms |
35916 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 6 |
Runtime error |
177 ms |
38512 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
117 ms |
31220 KB |
Output is correct |
| 8 |
Runtime error |
225 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
233 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
181 ms |
35284 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
