Submission #986901

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986901	2024-05-21T14:10:53 Z	mimi	Harbingers (CEOI09_harbingers)	C++17	100 / 100	91 ms	31248 KB

harbingers

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int,int>;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5;
int n,cnt=1,sz;
vector <pii> adj[maxn];
pii a[maxn];
ll dp[maxn],h[maxn];

struct previous
{
    int sz,pos,val;
    int cur,pos1;
    ld val1;
};
previous mark[maxn];

struct CHT
{
    int n,sz=0,cur=1;
    ll a[maxn],b[maxn];
    int line [maxn];
    ld point [maxn];

    CHT(){
        point[0]=-1e18;}

    ld intersect (int x, int y){
        return (ld)1.0 * (b[x]-b[y])/(a[y]-a[x]);}

    void add(int i, int u)
    {
        mark[u].sz=sz;
        mark[u].cur=cur;
        if(sz>=2)
        {
            int l=1,r=sz-1,mid;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(intersect(i,line[mid])<intersect(i,line[mid-1]))     r=mid-1;
                else                                                    l=mid+1;
            }
            cur=max(1,cur-sz+l);
            sz=l;
        }
//        while(sz>0)
//        {
//            if(a[line[sz-1]]==a[i])
//            {
//                if(b[line[sz-1]]<=b[i])    break;
//                else
//                {
//                    --sz;
//                    if(sz>0)   --cur;
//                }
//            }
//            else
//            {
//                if(sz<2)   break;
//                if(intersect(i,line[sz-1])<intersect(i,line[sz-2]))
//                {
//                    --sz;
//                    if(sz>0)   --cur;
//                }
//                else    break;
//            }
//        }
        if(sz==0 or a[line[sz-1]]!=a[i])
        {
            if(sz>0)
            {
                mark[u].val1=point[cur];
                point[cur] = intersect(line[sz-1],i);
                mark[u].pos1=cur;
                ++cur;
            }
            mark[u].pos=sz;
            mark[u].val=line[sz];
            line[sz]=i;
            ++sz;
        }
    }

    void undo(int u)
    {
        sz=mark[u].sz;
        cur=mark[u].cur;
        line[mark[u].pos]=mark[u].val;
        point[mark[u].pos1]=mark[u].val1;
    }

    ll gt(ll x)
    {
        int id=upper_bound(point,point+cur,x)-point-1;
        return a[line[id]]*x+b[line[id]];
    }

};
CHT f;

void DFS(int u, int v)
{
    for(pii i:adj[u])
    {
        if(i.ff==v)  continue;
        h[i.ff]=h[u]+i.ss;
        DFS(i.ff,u);
    }
}

void DFS1(int u, int v)
{
    if(u!=1)
    {
        dp[u]=a[u].ss*h[u]+a[u].ff+f.gt(a[u].ss);
        f.a[cnt]=-h[u];
        f.b[cnt]=dp[u];
        f.add(cnt,u);
        ++cnt;
    }
    for(pii i:adj[u])
    {
        if(i.ff==v)  continue;
        DFS1(i.ff,u);
    }
    if(u!=1)    f.undo(u);
}

void input()
{
    cin>>n;
    for(int i=1,u,v,s;i<n;++i)
    {
        cin>>u>>v>>s;
        adj[u].pp({v,s});
        adj[v].pp({u,s});
    }
    for(int i=2,u,v;i<=n;++i)
    {
        cin>>u>>v;
        a[i]={u,v};
    }
    f.a[0]=0;
    f.b[0]=0;
    f.add(0,0);
    DFS(1,0);
    DFS1(1,0);
    for(int i=2;i<=n;++i)   cout<<dp[i]<<sp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15704 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	32 ms	21516 KB	Output is correct
4	Correct	53 ms	24860 KB	Output is correct
5	Correct	57 ms	27952 KB	Output is correct
6	Correct	80 ms	31248 KB	Output is correct
7	Correct	44 ms	22948 KB	Output is correct
8	Correct	89 ms	27344 KB	Output is correct
9	Correct	91 ms	29268 KB	Output is correct
10	Correct	81 ms	28368 KB	Output is correct