Submission #1203004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203004		Sir_Ahmed_Imran	Harbingers (CEOI09_harbingers)	C++20	70 / 100	172 ms	131072 KiB

harbingers

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll V[N];
ll d[N];
int s[N];
ll dp[N];
vector<pll> ad[N];
vector<pii> a[N];
vector<pll> lines;

bool lesser(pair<__int128, __int128> p, pair<__int128, __int128> q){
    return p.ff * q.ss < q.ff * p.ss;
}

bool comp(pll l1, pll l2, pll l3){
    return lesser({l2.ss - l3.ss, l3.ff - l2.ff}, {l1.ss - l2.ss, l2.ff - l1.ff});
}

void insert(pll l, int v){
    while(lines.size() > 1 && comp(lines[lines.size() - 2], lines.back(), l)){
        ad[v].append(lines.back());
        lines.pop_back();
    }
    lines.append(l);
}

ll get(pll l, ll x){
    return l.ff * x + l.ss;
}

ll query(int x){
    int ans = 0;
    for(int i = 524288; i > 0; i /= 2)
        if(ans + i < lines.size() && get(lines[ans + i], x) < get(lines[ans + i - 1], x))
            ans += i;
    return get(lines[ans], x);    
}

void dfs(int v, int u){
    if(v > 1)
        dp[v] = query(V[v]) + V[v] * d[v] + s[v];
    insert({-d[v], dp[v]}, v);
    for(auto & [i, j] : a[v]){
        if(i == u) continue;
        d[i] = d[v] + j;
        dfs(i, v);
    }
    lines.pop_back();
    while(!ad[v].empty()){
        lines.append(ad[v].back());
        ad[v].pop_back();
    }
}

void solve(){
    int n, p, q, r;
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> p >> q >> r;
        a[p].append({q, r});
        a[q].append({p, r});
    }
    for(int i = 2; i <= n; i++){
        cin >> p >> q;
        s[i] = p, V[i] = q;
    }
    dfs(1, 0);
    for(int i = 2; i <= n; i++)
        cout << dp[i] << ' ';
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 70 / 100