Submission #395043

#	Time	Username	Problem	Language	Result	Execution time	Memory
395043		ocarima	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1083 ms	25980 KiB

harbingers

#include<bits/stdc++.h>

using namespace std;

#define lli long long
#define rep(x, a, b) for(lli x = (a); x <= (b); ++x)
#define debugsl(x) cout << #x << " = " << x << "; "
#define debug(x) debugsl(x); cout << endl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ix, a, b) cout << x[ix] << ", "; cout << "]" << endl
#define nl "\n"

#define MAX_N 100003
#define INF 1e18
#define in cin
#define out cout

#define ciudad first
#define distancia second

long double pre[MAX_N], sig[MAX_N];

struct rec{
    int ind;
    bool operator<(const rec& a) const{
        if (pre[ind] == pre[a.ind]) return sig[ind] < sig[a.ind];
        else return pre[ind] < pre[a.ind];
    }

    rec(int x)
        : ind(x){};
};

lli n, a, b, d, v[MAX_N], s[MAX_N], pos[MAX_N], dp[MAX_N];
vector<pair<lli, lli> > hijos[MAX_N];
set<rec> ch;
bool buscapunto;

#define eval(r, p) ((-pos[r])*p + dp[r])
#define cruce(r1, r2) ((dp[r2] - dp[r1] + 0.0) / (pos[r2] - pos[r1] + 0.0))

lli optimoch(lli nodo){
    pre[n + 1] = v[nodo];
    auto it = (--ch.upper_bound({n + 1}));
    return eval((*it).ind, v[nodo]);
}

void dfs(lli nodo, lli padre, lli posicion){

    vector<rec> tmp;
    lli r;

    pos[nodo] = posicion; // ASIGNALE SU POSICION

    // CALCULA EL OPTIMO PARA ESTE NODO
    dp[nodo] = optimoch(nodo) + s[nodo] + (v[nodo] * pos[nodo]);

    // METE SU LINEA AL CONVEX HULL
    // LAS LINEAS VAN AL FINAL
    auto it = (--ch.end());
    while (nodo != 1 && !ch.empty() && pre[(*it).ind] > cruce((*it).ind, nodo)){
        tmp.emplace_back(*it); // GUARDA LOS QUE ELIMINAS PARA DESPUES VOLVERLOS A INSERTAR Y QUE QUEDE IGUAL
        ch.erase(next(--it));
    }

    if (nodo != 1 && !ch.empty()){
        it = (--ch.end());

        r = (*it).ind;
        pre[nodo] = sig[r] = cruce(r, nodo);
        sig[nodo] = INF;

        ch.emplace_hint(ch.end(), nodo);
    }

    // BAJA A SUS HIJOS
    for (auto h : hijos[nodo]){
        if (h.ciudad == padre) continue;
        dfs(h.ciudad, nodo, posicion + h.distancia);
    }

    // ELIMINA SU LINEA DEL CONVEX HULL
    it = (--ch.end());
    if (nodo != 1 && (*it).ind == nodo){
        ch.erase(it);
        it = (--ch.end());

        r = (*it).ind;

        if (tmp.empty()) sig[r] = INF;
        else{
            sig[r] = pre[tmp.front().ind];
            for (auto r : tmp) ch.emplace_hint(ch.end(), r);
            tmp.clear();
        }
    }
}

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

    in >> n;
    rep(i, 1, n - 1){
        in >> a >> b >> d;
        hijos[a].emplace_back(b, d);
        hijos[b].emplace_back(a, d);
    }
    rep(i, 2, n) in >> s[i] >> v[i];

    sig[1] = INF;
    ch.emplace_hint(ch.end(), 1);

    dfs(1, 0, 0);

    rep(i, 2, n) out << dp[i] << " ";

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'long long int optimoch(long long int)':
harbingers.cpp:43:36: warning: narrowing conversion of '(n + 1)' from 'long long int' to 'int' [-Wnarrowing]
   43 |     auto it = (--ch.upper_bound({n + 1}));
      |                                  ~~^~~

• Subtask 1: 70 / 100