Submission #1103059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103059		ASN49K	Harbingers (CEOI09_harbingers)	C++14	100 / 100	118 ms	23844 KiB

harbingers

//solution with persistent cht(without needing to be amortized complexity because of rollback)
//the stratagy is that we use binary lifting(the O(n) option for better memory)
//https://codeforces.com/blog/entry/51684 (the blog for persistent cht)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
using i64=long long;
const int inf=1e9;
const i64 INF=1e18;
const int N=100'000;
const int LG=16;
struct line
{
    i64 a,b;
    i64 calc(int x)
    {
        return x*a+b;
    }
};
double intersect(const line& line1,const line& line2)
{
    //if(line1.a==line2.b)return -1e18;
    return (double)(line2.b-line1.b)/(double)(line1.a-line2.a);
}
bool better(const line& line1,const line& line2,const line& line3)
{
    return intersect(line1,line3)<=intersect(line1,line2);
}

struct edge
{
    int to,cost;
};
struct cht_node
{
    line l;
    int next,jump,jump_cnt;
};
int n;
int cost_start[N],cost_km[N];
i64 dp[N],h[N];
vector<cht_node>nodes;
vector<edge>adj[N];
void insert(int x,int parent)
{
    int cnt=0;
    while(parent!=0 && better(nodes[nodes[parent].next].l,nodes[parent].l,nodes[x].l))
    {
        cnt++;
        int jump=nodes[parent].jump;
        if(jump!=0 && better(nodes[nodes[jump].next].l,nodes[jump].l,nodes[x].l))
        {
            parent=jump;
        }
        else
        {
            parent=nodes[parent].next;
        }
    }
    assert(cnt<=100);
    nodes[x].next=parent;
    if(parent!=0 && nodes[parent].jump!=0 && nodes[parent].jump_cnt==nodes[nodes[parent].jump].jump_cnt)
    {
        nodes[x].jump=nodes[nodes[parent].jump].jump;
        nodes[x].jump_cnt=2*nodes[parent].jump_cnt+1;
    }
    else
    {
        nodes[x].jump=parent;
        nodes[x].jump_cnt=1;
    }
}

i64 query(int x,int cost)
{
    int cnt=0;
    while(x!=0 && intersect(nodes[nodes[x].next].l,nodes[x].l)>cost)
    {
        cnt++;
        int jump=nodes[x].jump;
        if(jump!=0 && intersect(nodes[nodes[jump].next].l,nodes[jump].l)>cost)
        {
            x=jump;
        }
        else
        {
            x=nodes[x].next;
        }
    }
    assert(cnt<=100);
    return nodes[x].l.calc(cost);
}
void dfs(int nod,int tt)
{
    for(auto &v:adj[nod])
    {
        if(v.to!=tt)
        {
            int c=v.to;
            h[c]=h[nod]+v.cost;
            dp[c]=h[c]*cost_km[c]+cost_start[c]-query(nod,cost_km[c]);
            nodes[c].l={h[c],-dp[c]};
            insert(c,nod);
            dfs(c,nod);
        }
    }
}
main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(nullptr);
    cin>>n;
    nodes.resize(n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        adj[x].pb({y,z});
        adj[y].pb({x,z});
    }
    for(int i=1;i<n;i++)
    {
        cin>>cost_start[i]>>cost_km[i];
    }
    nodes[0].l={0,0};
    dfs(0,0);
    for(int i=1;i<n;i++)cout<<dp[i]<<' ';
}

Compilation message (stderr)

harbingers.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main()
      | ^~~~

• Subtask 1: 100 / 100