oj.uz

Submission #445748

# Submission time Handle Problem Language Result Execution time Memory
445748 2021-07-19T13:04:23 Z stefantaga Harbingers (CEOI09_harbingers) C++14
100 / 100
 313 ms 21152 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 7 ms 3164 KB Output is correct
3 Correct 108 ms 10540 KB Output is correct
4 Correct 155 ms 14360 KB Output is correct
5 Correct 191 ms 17596 KB Output is correct
6 Correct 268 ms 21152 KB Output is correct
7 Correct 141 ms 11304 KB Output is correct
8 Correct 278 ms 16604 KB Output is correct
9 Correct 313 ms 18424 KB Output is correct
10 Correct 229 ms 17064 KB Output is correct