#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n;
vector< pair<int/*to*/,int/*size*/> > adj[nmax];
int depth[nmax];
long long dp[nmax];
int parent[nmax];
int start[nmax],speed[nmax];
void dfs(int node,int par)
{
for(auto k:adj[node])
if(k.first!=par)
{
depth[k.first]=depth[node]+k.second;
parent[k.first]=node;
dfs(k.first,node);
}
}
pair<int/*a*/,long long/*b*/> active[nmax];//ax+b
double cross(pair<int/*a*/,long long/*b*/> u,pair<int/*a*/,long long/*b*/> v)
{
return 1.0*(u.second-v.second)/(v.first-u.first);
}
long long ask(int pos,int x)
{
return 1LL*active[pos].first*x+active[pos].second;
}
int pointer=0;
long long ask_query(int x)
{
if(pointer==0)return 0;
long long ret=0;
ret=min(ret,ask(1,x));
ret=min(ret,ask(pointer,x));
int ok=0,not_ok=pointer;
while(not_ok-ok>1)
{
int av=(ok+not_ok)/2;
ret=min(ret,ask(av,x));
ret=min(ret,ask(av+1,x));
if(cross(active[av],active[av+1])<=x)ok=av;
else not_ok=av;
}
return ret;
}
void solve(int node,int par)
{
pair<int/*a*/,long long/*b*/> mem_active;
int mem_pointer;
if(node!=1)
{
dp[node]=ask_query(speed[node]);
dp[node]+=start[node]+1LL*depth[node]*speed[node];
pair<int/*a*/,long long/*b*/> current={-depth[node],dp[node]};
int ok=pointer,not_ok=0;
while(ok-not_ok>1)
{
int av=(ok+not_ok)/2;
if(cross(active[av],active[av+1])>=cross(active[av],current))ok=av;
else not_ok=av;
}
mem_active=active[ok+1];
mem_pointer=pointer;
pointer=ok+1;
active[pointer]=current;
}
for(auto k:adj[node])
if(k.first!=par)
{
solve(k.first,node);
}
if(node!=1)
{
active[pointer]=mem_active;
pointer=mem_pointer;
}
}
int main()
{
scanf("%i",&n);
int u,v,d;
for(int i=1;i<n;i++)
{
scanf("%i%i%i",&u,&v,&d);
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
for(int i=2;i<=n;i++)scanf("%i%i",&start[i],&speed[i]);
dfs(1,0);
solve(1,0);
for(int i=2;i<=n;i++)
{
printf("%lld",dp[i]);
if(i==n)printf("\n");
else printf(" ");
}
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
harbingers.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i%i",&u,&v,&d);
~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:114:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=2;i<=n;i++)scanf("%i%i",&start[i],&speed[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp: In function 'void solve(int, int)':
harbingers.cpp:99:16: warning: 'mem_pointer' may be used uninitialized in this function [-Wmaybe-uninitialized]
pointer=mem_pointer;
~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2688 KB |
Output is correct |
2 |
Correct |
8 ms |
3072 KB |
Output is correct |
3 |
Correct |
73 ms |
8824 KB |
Output is correct |
4 |
Correct |
117 ms |
11772 KB |
Output is correct |
5 |
Correct |
138 ms |
14072 KB |
Output is correct |
6 |
Correct |
146 ms |
16760 KB |
Output is correct |
7 |
Correct |
95 ms |
9420 KB |
Output is correct |
8 |
Correct |
171 ms |
13556 KB |
Output is correct |
9 |
Correct |
171 ms |
15352 KB |
Output is correct |
10 |
Correct |
168 ms |
14420 KB |
Output is correct |