Submission #718728

#	Time	Username	Problem	Language	Result	Execution time	Memory
718728		Ozy	Harbingers (CEOI09_harbingers)	C++17	100 / 100	172 ms	22908 KiB

harbingers

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#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 pll pair<lli,lli>

#define MAX 100000
#define MAXL 16
// para los hijos
#define des first
#define w second
//para el arreglo de lin
#define prep first
#define vel second
//para el convex hull
#define m first
#define ord second

lli n,a,b,c;
vector<pair<int, int> > hijos[MAX+2];
pair<int, int> lin[MAX+2];
pll ch[MAX+2];
lli anterior[MAX+2];
int ancestros[MAXL+1][MAX+2];
lli dp[MAX+2],prof[MAX+2];
int largo[MAX+2],lg[MAX+2];

lli cruce(pll a, pll b) {
    lli u = a.ord - b.ord;
    lli v = b.m - a.m;
    u /= v;
    return u;
}

void solve(int pos, int padre, lli p) {

    prof[pos] = p;

    // responde la pregunta para mi posicion
    lli x = padre;
    repa(i,lg[largo[padre]],0) if (anterior[ancestros[i][x]] >= lin[pos].vel) x = ancestros[i][x];
    if (anterior[x] >= lin[pos].vel) x = ancestros[0][x];

    dp[pos] = lin[pos].prep + prof[pos]*lin[pos].vel + dp[x] - prof[x]*lin[pos].vel;

    //hago mi propia línea
    ch[pos].ord = dp[pos];
    ch[pos].m = -prof[pos];

    //me integro en el convex hull trick con binaria
    x = padre;
    //CAMBIE while (x)
    //CAMBIE     if (cruce(ch[pos], ch[x]) <= anterior[x]) x = ancestros[0][x];
    //CAMBIE     else break;
    repa(i,lg[largo[padre]],0) if (cruce(ch[pos], ch[ancestros[i][x]]) <= anterior[ancestros[i][x]]) x = ancestros[0][ancestros[i][x]];
    if (cruce(ch[pos], ch[x]) <= anterior[x]) x = ancestros[0][x];

    ancestros[0][pos] = x;
    anterior[pos] = cruce(ch[pos], ch[x]);

    largo[pos] = largo[x] + 1;

    // ESTE ERA EL ERROR!!!! repa(i,1,18) {
    rep(i,1,lg[largo[pos]]) {
        ancestros[i][pos] = ancestros[i-1][x];
        x = ancestros[i][pos];
    }

    for(auto h : hijos[pos]) {
        if (h.des == padre) continue;
        solve(h.des,pos,p+h.w);
    }

}

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

    //PRECALCULA EL LOGARITMO DE TODOS LOS VALORES
    lg[0] = lg[1] = 1;
    rep(i,2,MAX) lg[i] = ((1 << (lg[i - 1] + 1)) > i) ? lg[i - 1] : lg[i - 1] + 1;

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

    largo[1] = 1;
    for (auto h : hijos[1]) {
        solve(h.des,1,h.w);
    }

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

    return 0;
}

• Subtask 1: 100 / 100