제출 #397239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397239		Ozy	Harbingers (CEOI09_harbingers)	C++17	0 / 100	245 ms	33232 KiB

harbingers

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int

#define debug(x) cout << #x << " = " << x << endl

#define des first
#define val second

lli n,a,b,c,j;
lli dist[100002], padres[20][100002], res[100002], vel[100002], prep[100002];
lli dp[100002];
vector<pair<lli,lli> > hijos[100002];
double cruce[100002];

struct linea{
    lli pend;
    lli ord;
};

double inter(linea l1, linea l2) {
    double resu;

    resu = l1.ord - l2.ord + 0.0;
    resu /= l2.pend -l1.pend;
    return resu;

}

struct CH{

    linea lineas[100002];

    lli agregalinea(lli i, lli j) {
        lineas[i] = {-dist[i], dp[i]};

        lli ult = j;

        repa(k,18,0) {
            if (padres[k][ult] == 0) continue;

            if (inter(lineas[i], lineas[padres[k][ult]]) < cruce[ padres[k][ult] ]) ult = padres[k][ult];
        }

        return ult;
    }

    lli query(lli pos, lli x) {
        lli ult = pos;

        repa(i,18,0) {
            if (padres[i][ult] == 0) continue;

            if (cruce[ padres[i][ult] ] > x) ult = padres[i][ult];
        }

        return ult;
    }

};

CH ch;

void DFS(lli pos, lli pas) {
    lli k;

    if (pos == 1) j = 0;
    else {
        j = ch.query(pas, vel[pos]);
        if (cruce[j] > vel[pos]) j = padres[0][j];
    }

    //debug(j);


    dp[pos] = -dist[j] * vel[pos] + dp[j] + prep[pos] + dist[pos] * vel[pos];

    if (pos != 1){
        j = ch.agregalinea(pos, pas);
        k = 1;
        padres[0][pos] = j;
        while(k < 20 && padres[k-1][ padres[k-1][pos] ] > 0) {
            padres[k][pos] = padres[k-1][ padres[k-1][pos] ];
            k++;
        }
        cruce[pos] = inter({-dist[j], dp[j]}, {-dist[pos], dp[pos]});
    }

    for (auto h : hijos[pos]) {
        if (h.des == pas) continue;

        dist[h.des] = h.val;
        dist[h.des] += dist[pos];
        DFS(h.des,pos);
    }


}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    rep(i,1,n - 1) {
        cin >> a >> b >> c;
        hijos[a].push_back({b,c});
        hijos[b].push_back({a,c});
    }
    rep(i,2,n) cin >> prep[i] >> vel[i];

    DFS(1,0);

    rep(i,2,n) cout << dp[i] << ' ';
}

• Subtask 1: 0 / 100