Submission #1139881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139881		LeonidCuk	Harbingers (CEOI09_harbingers)	C++20	20 / 100	208 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[100000],v;
long long dp[100000];
struct node
{
    long long int a,b;
    node *l,*r;
    node(long long int a1,long long int b1)
    {
        a=a1;
        b=b1;
        l=nullptr;
        r=nullptr;
    }

};
node *root[100000];
long long int najdi(node *n,long long int x)
{
    return n->a*x+n->b;
}
void smeni(node *a,node *b)
{
    swap(a->a,b->a);
    swap(a->b,b->b);
}
long long int gsum(node *n,int l,int r,long long int x)
{
    if(l==r)return najdi(n,x);
    int m=(l+r)/2;
    if(x<=m)
    {
        if(n->l==nullptr)return najdi(n,x);
        else return min(najdi(n,x),gsum(n->l,l,m,x));
    }
    else
    {
        if(n->r==nullptr)return najdi(n,x);
        else return min(najdi(n,x),gsum(n->r,m+1,r,x));
    }
}
node *update(node *n,int l,int r,node *x)
{
    node *t=new node(n->a,n->b);
    int m=(l+r)/2;
    if(t->a<x->a)smeni(x,t);
    if(l==r)
    {
        if(najdi(x,m)>najdi(t,m))return t;
        else return x;
    }
    if(najdi(x,m)>najdi(t,m))
    {
        t->l=n->l;
        if(n->r==nullptr)t->r=x;
        else t->r=update(n->r,m+1,r,x);
    }
    else
    {
        smeni(x,t);
        t->r=n->r;
        if(n->l==nullptr)t->l=x;
        else t->l=update(n->l,l,m,x);
    }
    return t;
}
void dfs(int a,int b,long long int sum)
{
    dp[a]=v[a].first+sum*v[a].second+gsum(root[b],0,1000000000,v[a].second);
    node *t=new node(-sum,dp[a]);
    root[a]=update(root[b],0,1000000000,t);
    for(auto i:g[a])
    {
        if(i.first!=b)
        {
            dfs(i.first,a,i.second+sum);
        }
    }
}
int main()
{
    int n,a,b,c;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>a>>b>>c;
        g[a-1].push_back({b-1,c});
        g[b-1].push_back({a-1,c});
    }
    root[0]=new node(0LL,0LL);
    v.push_back({0,0});
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        v.push_back({a,b});
    }
    dfs(0,0,0);
    for(int i=1;i<n;i++)
    {
        cout<<dp[i]<<" ";
    }
    return 0;
}

• Subtask 1: 20 / 100