Submission #1067305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067305		parlimoos	Harbingers (CEOI09_harbingers)	C++14	100 / 100	80 ms	29780 KiB

harbingers

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

struct line{
    ll ar , sh , x;
};

const ll INF = (1ll * 1e18);

int n;
vector<arr(2)> tr[100000];
ll ps[100000] , dp[100000] , inf[100000][2];
int bl[100000][20];
line ls[100000];

bool isDel(int a , int b , int c){
    __int128_t d1 = (ls[a].ar - ls[b].ar) , d2 = (ls[b].sh - ls[a].sh);
    __int128_t d3 = (ls[b].ar - ls[c].ar) , d4 = (ls[c].sh - ls[b].sh);
    __int128_t dd = -1;
    if(d2 < 0ll) d1 *= dd , d2 *= dd;
    if(d4 < 0ll) d3 *= dd , d4 *= dd;
    return ((d1 * d4) <= (d2 * d3));
}
ll getX(int a , int b){
    ll d1 = (ls[a].ar - ls[b].ar) , d2 = (ls[b].sh - ls[a].sh);
    if(d2 < 0ll) d1 *= (-1ll) , d2 *= (-1ll);
    return ((d1 + d2 - 1ll) / d2);
}
int getLine(int v , ll i){
    // while(ls[v].x > i) v = bl[v][0];
    // return v;
    if(ls[v].x <= i) return v;
    for(int bit = 19 ; bit >= 0 ; bit--){
        if(bl[v][bit] == -1) continue;
        int ln = bl[v][bit];
        if(ls[ln].x > i) v = ln;
    }
    return bl[v][0];
}
int addLine(int v , int p){
    // while(p != 0 and isDel(v , p , bl[p][0])) p = bl[p][0];
    // return p;
    if(p == 0) return p;
    if(!isDel(v , p , bl[p][0])) return p;
    for(int bit = 19 ; bit >= 0 ; bit--){
        int ln = bl[p][bit];
        if(ln == -1 or ln == 0) continue;
        if(isDel(v , ln , bl[ln][0])) p = ln;
    }
    // if(p == 0) cout << inf[v][1] << "$$\n";
    return bl[p][0];
}
void dfs1(int v = 0 , int p = -1){
    if(p != -1) ps[v] += ps[p];
    for(auto e : tr[v]){
        if(e[0] == p) continue;
        ps[e[0]] = e[1] , dfs1(e[0] , v);
    }
}
void dfs2(int v = 0 , int p = -1){
    // cout << v << "^^\n" << flush;
    if(v == 0){
        dp[0] = 0 , ls[0].x = 0;
        ls[0].ar = 0 , ls[0].sh = 0;
        for(int bit = 0 ; bit < 20 ; bit++) bl[0][bit] = -1;
    }else{
        int j = getLine(p , inf[v][1]);
        // cout << v << " : " << j << "%\n";
        dp[v] = (ps[v] - ps[j]) * inf[v][1] + inf[v][0] + dp[j];
        ls[v].sh = -(ps[v]) , ls[v].ar = dp[v];
        j = addLine(v , p) , bl[v][0] = j;
        // cout << v << " :: " << j << "$\n";
        for(int bit = 1 ; bit < 20 ; bit++){
            if(bl[v][bit - 1] == -1) bl[v][bit] = -1;
            else bl[v][bit] = bl[bl[v][bit - 1]][bit - 1];
        }
        ls[v].x = getX(v , j);
        // cout << v << " " << getX(v , j) << "@@\n" << flush;
    }
    for(auto e : tr[v]){
        if(e[0] == p) continue;
        dfs2(e[0] , v);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("out.txt" , "r" , stdin);
    // freopen("ans.txt" , "w" , stdout);

    cin >> n;
    for(int i = 1 ; i < n ; i++){
        int v , u , d;
        cin >> v >> u >> d;
        tr[v - 1].pb({u - 1 , d}) , tr[u - 1].pb({v - 1 , d});
    }
    for(int i = 1 ; i < n ; i++) cin >> inf[i][0] >> inf[i][1];
    dfs1();
    // for(int v = 0 ; v < n ; v++) cout << v << " : " << ps[v] << "&&\n";
    dfs2();
    for(int v = 1 ; v < n ; v++) cout << dp[v] << " ";
}

• Subtask 1: 100 / 100