#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long L;
typedef vector< L > vL;
typedef vector< vL > vvL;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
const int inf = 1e9;
const L inf8 = 1e18;
const int maxn = 1e5 + 5;
vii adj[maxn];
int s[maxn], v[maxn];
int dp[25][maxn];
int Depth[maxn];
L res[maxn];
struct node
{
L m, b;
node(L x, L y)
{
m = x; b = y;
}
};
node* root[maxn];
int getAnc(int lev, int u)
{
for(int i = 20; i>= 0; i--)
{
if((1<<i)<= lev)
{
lev -= (1<<i);
u = dp[i][u];
}
}
return u;
}
double getInt(node *A, node *B)
{
double m1 = A->m, b1 = A->b;
double m2 = B->m, b2 = B->b;
return (double) (b2-b1)/(m1-m2);
}
L eval(node *A, L x)
{
return A->m*x + A->b;
}
L query(int to, L x, int dep)
{
if(dep == 1)
{
return eval(root[to], x);
}
//printf("%d %lld %d\n", to, x, dep);
if(dep>= 2)
{
int here = getAnc(dep-2, to);
if((double) x<= getInt(root[1], root[here])) return eval(root[1], x);
}
int lo = 0, hi = dep-2;
//printf("correct\n");
while(lo< hi)
{
int mid = (lo+hi)/2;
int x2 = getAnc(mid, to);
int x1 = dp[0][x2];
double Int = getInt(root[x1], root[x2]);
//printf("trying %d\n", x1);
//cout << Int << endl;
if(Int<= (double) x) hi = mid;
else lo = mid+1;
}
//printf("lo is %d\n", lo);
//printf("getAnc is %d\n", getAnc(lo, to));
return eval(root[getAnc(lo, to)], x);
}
bool bad(node *A, node *B, node *C)
{
double m1 = A->m, b1 = A->b;
double m2 = B->m, b2 = B->b;
double m3 = C->m, b3 = C->b;
double x1 = (double) (b3-b1)/(m1-m3);
double x2 = (double) (b1-b2)/(m2-m1);
return x1<= x2;
}
int add(int to, int adder)
{
int d = Depth[to];
int lo = 0, hi = d-1;
if(d < 2) return to;
while(lo< hi)
{
int mid = (lo+hi)/2;
int x2 = getAnc(mid, to);
int x1 = dp[0][x2];
if(x1 == 0) hi = mid;
else if(bad(root[x1], root[x2], root[adder])) lo = mid+1;
else hi = mid;
}
return getAnc(lo, to);
}
void solve(int u, int p, L dist)
{
//printf("%d\n", u);
res[u] = query(p, v[u], Depth[p]) + dist*v[u]+s[u];
//printf("query with %d\n", v[u]);
//printf("%lld\n",query(p, v[u], Depth[p]));
//printf("...\n");
root[u] = new node(-dist, res[u]);
//printf("insert! %lld %lld\n", -dist, res[u]);
int k = add(p, u);
//printf("k is %d\n", k);
Depth[u] = Depth[k]+1;
dp[0][u] = k;
for(int i = 1; i<= 20; i++) dp[i][u] = dp[i-1][dp[i-1][u]];
for(auto kk : adj[u])
{
int v = kk.X, w = kk.Y;
if(v == p) continue;
solve(v, u, dist+w);
}
}
int main()
{
int n; scanf("%d", &n);
for(int i = 0; i< n-1; i++)
{
int a, b, w; scanf("%d %d %d", &a, &b, &w);
adj[a].pb(ii(b, w)); adj[b].pb(ii(a, w));
}
for(int i = 2; i<= n; i++)
{
scanf("%d %d", s+i, v+i);
}
root[1] = new node(0, 0);
Depth[1] = 1;
for(auto kk : adj[1])
{
solve(kk.X, 1, kk.Y);
}
for(int i = 2; i<= n; i++) printf("%lld ", res[i]);
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
harbingers.cpp:134:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, w; scanf("%d %d %d", &a, &b, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", s+i, v+i);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3448 KB |
Output is correct |
| 3 |
Correct |
124 ms |
13484 KB |
Output is correct |
| 4 |
Correct |
223 ms |
18428 KB |
Output is correct |
| 5 |
Correct |
185 ms |
23388 KB |
Output is correct |
| 6 |
Correct |
223 ms |
27896 KB |
Output is correct |
| 7 |
Correct |
164 ms |
18712 KB |
Output is correct |
| 8 |
Correct |
514 ms |
25948 KB |
Output is correct |
| 9 |
Correct |
614 ms |
26888 KB |
Output is correct |
| 10 |
Correct |
457 ms |
25972 KB |
Output is correct |
