#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define prl(x) printf("%lld\n",x)
#define yes printf("YES\n")
#define no printf ("NO\n")
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define s second
#define tmp (l+r)/2
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ld pi=2*acos(0);
const ll mod=1e9+7;
const ld eps=1e-9;
const ll ll_max=4e18;
///const ll mod=998244353;
/// make the equation y=m*x+p+g
/// where g is constant and y==dp[i]
/// dp[i]=query(x)+g;
/// Line l={m,p};
/// insert(node*,l);
/// if you want max
/// dp[i]=-query(x)+g;
/// Line l={-m,-p};
/// insert(node* ,l);
using namespace std;
const ll RANG = 1e9;
struct Line{
ll m,p;
Line(){
m=0;
p=ll_max;
}
}fai;
struct node{
Line line;
node *l;
node *r;
node(Line line2=fai,node *l2=NULL,node *r2=NULL)
{
line=line2;
l=l2;
r=r2;
}
};
ll f(Line l,ll x){
return l.m*x+l.p;
}
node* insert(node *cur,Line line,ll st=1,ll en=RANG)
{
node *ret=new node(cur->line,cur->l,cur->r);
ll m=st+(en-st)/2ll;
bool left = f(line, st) < f(ret->line, st);
bool mid = f(line, m) < f(ret->line, m);
if(mid)
swap(line,ret->line);
if(ret->l==NULL)
ret->l=new node();
if(ret->r==NULL)
ret->r=new node();
if(en - st == 0)
{
return ret;
}
else if(left != mid)
{
node *left=insert(ret->l,line,st,m);
ret->l=left;
return ret;
}
else
{
node *right=insert(ret->r,line,m+1,en);
ret->r=right;
return ret;
}
}
ll query(node *cur,ll x,ll st=1,ll en=RANG)
{
ll m = st+(en-st)/2ll;
ll curr = f(cur->line, x);
if(en-st==0) return curr;
if(cur->l==NULL)
cur->l=new node();
if(cur->r==NULL)
cur->r=new node();
if(x<m) return min(curr, query(cur->l,x, st, m));
else return min(curr, query(cur->r,x, m+1, en));
}
int n;
ll s[100001];
ll v[100001];
vector<pair<int,ll>>vec[100001];
node *root[100001];
ll dist[100001];
ll mem[100001];
void dfs(int city,int par,ll q)
{
if(city!=1)
{
dist[city]=dist[par]+q;
mem[city]=(query(root[par],v[city])+dist[city]*v[city])+s[city];
root[city]=root[par];
Line l;
l.m=-dist[city];
l.p=mem[city];
root[city]=insert(root[city],l);
}
for(auto c:vec[city])
{
if(c.f==par)
continue;
dfs(c.f,city,c.s);
}
}
int main()
{
root[1]=new node();
Line l;
l.m=l.p=0;
root[1]=insert(root[1],l);
sc(n);
for(int i=0;i<n-1;i++)
{
int x,y;
ll c;
sc(x);sc(y);scl(c);
vec[x].pb({y,c});
vec[y].pb({x,c});
}
for(int i=2;i<=n;i++)
{
scl(s[i]);
scl(v[i]);
}
dfs(1,0,0);
for(int i=2;i<=n;i++)
printf("%lld ",mem[i]);
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:131:5: note: in expansion of macro 'sc'
131 | sc(n);
| ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:136:9: note: in expansion of macro 'sc'
136 | sc(x);sc(y);scl(c);
| ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:136:15: note: in expansion of macro 'sc'
136 | sc(x);sc(y);scl(c);
| ^~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:136:21: note: in expansion of macro 'scl'
136 | sc(x);sc(y);scl(c);
| ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:142:9: note: in expansion of macro 'scl'
142 | scl(s[i]);
| ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:143:9: note: in expansion of macro 'scl'
143 | scl(v[i]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2900 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6612 KB |
Output is correct |
| 3 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
113 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
129 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
138 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
111 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
144 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
134 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
121 ms |
65536 KB |
Execution killed with signal 9 |
