제출 #1196722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196722		Sir_Ahmed_Imran	Harbingers (CEOI09_harbingers)	C++20	60 / 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)
#define int __int128

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

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

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

void insert(pii 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(pii l, int 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];
    pii pi = {-d[v], dp[v]};
    insert(pi, 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(){
    ll 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++){
        r = dp[i];
        cout << r << ' ';
    }
}

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

• Subtask 1: 60 / 100