#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
/*
Let anc[u][x] be the x'th ancestor of u.
dp[u] =def= amount of time needed for message to be delivered from u to 1.
dp[1] =def= 0
dp[u] = min{S[u] + V[u]*dist(u, v) + dp[v] | v in anc[u]}
= min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v in anc[u]}
dp[u] min= S[u] + V[u]*dist1[u] + -dist1[v]*V[u] + dp[v]
a * x + b
*/
long long INF = 1e9;
vector<long long> edge[100001], dist[100001]; //edges, weights of edges
vector<long long> S(100001, 0), V(100001, 0); //starting time, reciprocal speed
vector<long long> dist1(100001, 0);
long long cht_anc[100001][19];
vector<long long> prev_node(100001), prev_dist(100001);
void dfs1(long long u)
{
for(long long i = 0; i < edge[u].size(); i++)
{
long long v = edge[u][i];
long long d = dist[u][i];
if(prev_node[u] == v) continue;
prev_node[v] = u;
prev_dist[v] = d;
dist1[v] = dist1[u] + prev_dist[v];
dfs1(v);
}
}
vector<long long> a(100001), b(1000001);
vector<long long> dp(100001);
bool intersect_comp(long long e1, long long e2, long long x) //intersect(w, x) < long longesect(y, z)?
{ /*a[e1]*x + b[e1] = a[e2]*x + b[e2]
x_e = (b[e2] - b[e1])/(a[e1] - a[e2])
*/
return (b[e2] - b[e1]) < (a[e1] - a[e2])*x; //Be very careful with the sign.
}
bool line_intersect_comp(long long e1, long long e2, long long f1, long long f2)
{//long longersect(e1, e2) < long longersect(f1, f2)
if(e2 == 1) return 1;
return (b[e2] - b[e1])*(a[f1] - a[f2]) < (b[f2] - b[f1])*(a[e1] - a[e2]);
}
/*
i, i+1, L
Line i+2 is a good insertion if long longersect(i, i+1) < long longersect(i+1, i+2)
We need to binary search for the largest line i such that long longersect(i-1, i) < long longersect(i, L)
*/
void dfs2(long long u)
{
for(long long v: edge[u])
{
if(prev_node[u] == v) continue;
/*w is the ideal harbinger for the harbinger from v to go to
Using binary lifting, we search for the edge on which f(x) is maximised
*/
// long long w = prev_node[v];
// for(long long e = 18; e >= 0; e--)
// {
// if(cht_anc[w][e] == 1) continue;
// if(long longersect_comp( prev_node[cht_anc[w][e]] , cht_anc[w][e] ) == 1)
// w = cht_anc[w][e];
// }
//
// dp[v] = S[v] + V[v]*(dist1[v] - dist1[w]) + dp[w];
//
// a[v] = -dist1[v];
// b[v] = dp[v];
//
// w = prev_node[v];
// for(long long e = 18; e >= 0; e--)
// {
// long long temp = cht_anc[w][e];
// if(line_long longersect_comp(prev_node[temp], temp, temp, v))
// continue;
// w = temp;
// }
//
// if(!line_long longersect_comp(prev_node[w], w, w, v))
// w = cht_anc[w][0];
//
// cht_anc[v][0] = w;
// for(long long e = 1; e <= 18; e++)
// cht_anc[v][e] = cht_anc[ cht_anc[v][e-1] ][e-1];
dp[v] = INF;
for(long long w = prev_node[v]; 1; w = prev_node[w])
{
dp[v] = min(dp[v], S[v] + V[v]*(dist1[v] - dist1[w]) + dp[w]);
if(w == 1) break;
}
dfs2(v);
}
}
int main()
{
long long N;
cin >> N;
for(long long j = 1; j <= N-1; j++)
{
long long u, v, d;
cin >> u >> v >> d;
edge[u].push_back(v);
dist[u].push_back(d);
edge[v].push_back(u);
dist[v].push_back(d);
}
for(long long i = 2; i <= N; i++)
cin >> S[i] >> V[i];
prev_node[1] = 1;
prev_dist[1] = 0;
dfs1(1);
// for(long long i = 1; i <= N; i++)
// {
// cerr << "i = " << i << ": ";
// cerr << S[i] << ' ' << V[i] << ' ' << dist1[i] << " " << prev_node[i] << ' ' << prev_dist[i] << '\n';
// }
dp[1] = 0;
for(long long e = 0; e <= 18; e++)
cht_anc[1][e] = 1;
V[1] = S[1] = 0;
dfs2(1);
for(long long i = 2; i <= N; i++) cout << dp[i] << ' ';
cout << '\n';
}
Compilation message
harbingers.cpp: In function 'void dfs1(long long int)':
harbingers.cpp:28:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(long long i = 0; i < edge[u].size(); i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
18252 KB |
Output is correct |
| 2 |
Correct |
32 ms |
18684 KB |
Output is correct |
| 3 |
Execution timed out |
1097 ms |
24660 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1095 ms |
27320 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1090 ms |
30532 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1038 ms |
33308 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1089 ms |
26272 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1094 ms |
29768 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1093 ms |
31428 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1087 ms |
30608 KB |
Time limit exceeded |
