Submission #445748

#	Time	Username	Problem	Language	Result	Execution time	Memory
445748		stefantaga	Harbingers (CEOI09_harbingers)	C++14	100 / 100	313 ms	21152 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
struct wow
{
    long long s,v;
}sal[100005];
vector <pair <long long ,long long  > > v[100005];
long long i,n,x,y,cost,din[100005],dist[100005];
void dfs(long long  x,long long  tata)
{
    long long  i;
    for (i=0;i<v[x].size();i++)
    {
        long long  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 (double)(b.b-a.b)/(a.a-b.a);
}
long long  q;
void dfsfin(long long  x,long long  tata)
{
    long long  st=0,dr=q;
    while (st!=dr)
    {
        long long  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)
    {
        long long  mij=(st+dr)/2;
        if (intersectie(stiva[mij],stiva[mij+1])>=intersectie(stiva[mij],acum))
        {
            dr=mij;
        }
        else
        {
            st=mij+1;
        }
    }
    long long  inainte=q;
    linie ocupata=stiva[st+1];
    stiva[st+1]=acum;
    q=st+1;
    for (long long  i=0;i<v[x].size();i++)
    {
        long long  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 (stderr)

harbingers.cpp: In function 'void dfs(long long int, long long int)':
harbingers.cpp:13:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (i=0;i<v[x].size();i++)
      |              ~^~~~~~~~~~~~
harbingers.cpp: In function 'void dfsfin(long long int, long long int)':
harbingers.cpp:67:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (long long  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<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (i=0;i<v[1].size();i++)
      |              ~^~~~~~~~~~~~

• Subtask 1: 100 / 100