#include <bits/stdc++.h>
using namespace std;
struct wow
{
long long s,v;
}sal[100005];
vector <pair <int,int > > v[100005];
long long i,n,x,y,cost,din[100005],dist[100005];
void dfs(int x,int tata)
{
int i;
for (i=0;i<v[x].size();i++)
{
int nod=v[x][i].first;
if (nod!=tata)
{
dist[nod]=dist[x]+v[x][i].second;
dfs(nod,x);
}
}
}
struct linie
{
long long a,b;
}stiva[100005];
double intersectie(linie a,linie b)
{
return (b.b-a.b)/(a.a-b.a);
}
int q;
void dfsfin(int x,int tata)
{
int st=0,dr=q;
while (st!=dr)
{
int mij=(st+dr)/2;
if (intersectie(stiva[mij],stiva[mij+1])>=sal[x].v)
{
dr=mij;
}
else
{
st=mij+1;
}
}
din[x]=sal[x].s+sal[x].v*dist[x]+stiva[st].a*sal[x].v+stiva[st].b;
linie acum={-dist[x],din[x]};
st=0;
dr=q;
while (st!=dr)
{
int mij=(st+dr)/2;
if (intersectie(stiva[mij],stiva[mij+1])>=intersectie(stiva[mij],acum))
{
dr=mij;
}
else
{
st=mij+1;
}
}
int inainte=q;
linie ocupata=stiva[st+1];
stiva[st+1]=acum;
q=st+1;
for (int i=0;i<v[x].size();i++)
{
int nod=v[x][i].first;
if (nod!=tata)
{
dfsfin(nod,x);
}
}
stiva[st+1]=ocupata;
q=inainte;
}
int main()
{
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n;
for (i=1;i<=n-1;i++)
{
cin>>x>>y>>cost;
v[x].push_back({y,cost});
v[y].push_back({x,cost});
}
for (i=2;i<=n;i++)
{
cin>>sal[i].s>>sal[i].v;
}
dfs(1,0);
for (i=0;i<v[1].size();i++)
{
dfsfin(v[1][i].first,1);
}
for (i=2;i<=n;i++)
{
cout<<din[i]<<" ";
}
return 0;
}
Compilation message
harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
harbingers.cpp: In function 'void dfsfin(int, int)':
harbingers.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:96:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (i=0;i<v[1].size();i++)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Incorrect |
6 ms |
3148 KB |
Output isn't correct |
3 |
Correct |
125 ms |
11596 KB |
Output is correct |
4 |
Incorrect |
178 ms |
15520 KB |
Output isn't correct |
5 |
Correct |
207 ms |
19352 KB |
Output is correct |
6 |
Incorrect |
253 ms |
23120 KB |
Output isn't correct |
7 |
Incorrect |
162 ms |
12484 KB |
Output isn't correct |
8 |
Incorrect |
267 ms |
17712 KB |
Output isn't correct |
9 |
Correct |
272 ms |
20176 KB |
Output is correct |
10 |
Incorrect |
256 ms |
18716 KB |
Output isn't correct |