#include <stdio.h>
#include <stdlib.h>
#define N 100000
#define LN 16 /* LN = floor(log2(N - 1)) */
int min(int a, int b) { return a < b ? a : b; }
int *ej[N], *ew[N], eo[N];
void append(int i, int j, int w) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0) {
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
}
ej[i][o] = j, ew[i][o] = w;
}
int pp[N][LN + 1], dd[N], ss[N], vv[N]; long long xx[N], yy[N];
double cross(int i, int j, int k) {
return (double) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (double) (xx[k] - xx[i]) * (yy[j] - yy[i]);
}
void dfs(int p, int i, int d, long long x) {
int o, h;
dd[i] = d, xx[i] = x;
if (i > 0) {
int j;
for (h = LN, j = p; h >= 0; h--) {
int j_ = pp[j][h];
if (j_ != -1 && pp[j_][0] != -1 && yy[j_] + (xx[i] - xx[j_]) * vv[i] >= yy[pp[j_][0]] + (xx[i] - xx[pp[j_][0]]) * vv[i])
j = j_;
}
if (pp[j][0] != -1 && yy[j] + (xx[i] - xx[j]) * vv[i] >= yy[pp[j][0]] + (xx[i] - xx[pp[j][0]]) * vv[i])
j = pp[j][0];
yy[i] = yy[j] + (xx[i] - xx[j]) * vv[i] + ss[i];
for (h = LN, j = p; h >= 0; h--) {
int j_ = pp[j][h];
if (j_ != -1 && pp[j_][0] != -1 && cross(pp[j_][0], j_, i) <= 0)
j = j_;
}
if (j != -1 && pp[j][0] != -1 && cross(pp[j][0], j, i) <= 0)
j = pp[j][0];
pp[i][0] = j;
} else
pp[i][0] = -1;
for (h = 0; h < LN; h++)
pp[i][h + 1] = pp[i][h] == -1 ? -1 : pp[pp[i][h]][h];
for (o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
if (j != p)
dfs(i, j, d + 1, x + w);
}
}
int main() {
int n, h, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
ew[i] = (int *) malloc(2 * sizeof *ew[i]);
}
for (h = 0; h < n - 1; h++) {
int w;
scanf("%d%d%d", &i, &j, &w), i--, j--;
append(i, j, w), append(j, i, w);
}
for (i = 1; i < n; i++)
scanf("%d%d", &ss[i], &vv[i]);
dfs(-1, 0, 0, 0);
for (i = 1; i < n; i++)
printf("%lld ", yy[i]);
printf("\n");
return 0;
}
Compilation message
harbingers.c: In function 'append':
harbingers.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
14 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
harbingers.c: In function 'main':
harbingers.c:67:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
harbingers.c:75:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d%d%d", &i, &j, &w), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d", &ss[i], &vv[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
936 KB |
Output is correct |
| 3 |
Correct |
55 ms |
12492 KB |
Output is correct |
| 4 |
Correct |
92 ms |
17812 KB |
Output is correct |
| 5 |
Correct |
128 ms |
23624 KB |
Output is correct |
| 6 |
Correct |
120 ms |
28988 KB |
Output is correct |
| 7 |
Correct |
85 ms |
17116 KB |
Output is correct |
| 8 |
Correct |
176 ms |
25020 KB |
Output is correct |
| 9 |
Correct |
180 ms |
26652 KB |
Output is correct |
| 10 |
Correct |
184 ms |
25456 KB |
Output is correct |
