Submission #395010

#	Time	Username	Problem	Language	Result	Execution time	Memory
395010		ocarima	Harbingers (CEOI09_harbingers)	C++14	60 / 100	1100 ms	36700 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 (1 << 60)
#define in cin
#define out cout

#define ciudad first
#define distancia second
#define cruceprevio first.first
#define crucesig first.second
#define recta second

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<pair<pair<double, double>, lli> > ch;

#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 x){
    auto it = (--ch.upper_bound({{x, 0}, 0}));
    return eval((*it).recta, x);
}

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

    set<pair<pair<double, double>, lli> > tmp;
    double pre, sig;
    lli r;

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

    // CALCULA EL OPTIMO PARA ESTE NODO
    dp[nodo] = optimoch(v[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() && (*it).cruceprevio > cruce((*it).recta, nodo)){
        pre = (*it).cruceprevio;
        sig = (*it).crucesig;
        r = (*it).recta;

        tmp.emplace_hint(tmp.begin(), (*it)); // GUARDA LOS QUE ELIMINAS PARA DESPUES VOLVERLOS A INSERTAR Y QUE QUEDE IGUAL
        ch.erase(it);
        it = (--ch.end());
    }

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

        pre = (*it).cruceprevio;
        sig = (*it).crucesig;
        r = (*it).recta;

        ch.erase(it);
        sig = cruce((*it).recta, nodo);

        ch.insert({{pre, sig}, r});
        ch.insert({{sig, INF}, 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).recta == nodo){
        ch.erase(it);
        it = (--ch.end());

        pre = (*it).cruceprevio;
        sig = (*it).crucesig;
        r = (*it).recta;

        ch.erase(it);

        if (tmp.empty()) ch.insert({{pre, INF}, r});
        else{
            ch.insert({{pre, (*tmp.begin()).cruceprevio}, r});
            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];
    ch.emplace_hint(ch.end(), make_pair(0, INF), 1);

    dfs(1, 0, 0);

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

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:13:19: warning: left shift count >= width of type [-Wshift-count-overflow]
   13 | #define INF (1 << 60)
      |                   ^~
harbingers.cpp:70:26: note: in expansion of macro 'INF'
   70 |         ch.insert({{sig, INF}, nodo});
      |                          ^~~
harbingers.cpp:13:19: warning: left shift count >= width of type [-Wshift-count-overflow]
   13 | #define INF (1 << 60)
      |                   ^~
harbingers.cpp:91:43: note: in expansion of macro 'INF'
   91 |         if (tmp.empty()) ch.insert({{pre, INF}, r});
      |                                           ^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:13:19: warning: left shift count >= width of type [-Wshift-count-overflow]
   13 | #define INF (1 << 60)
      |                   ^~
harbingers.cpp:111:44: note: in expansion of macro 'INF'
  111 |     ch.emplace_hint(ch.end(), make_pair(0, INF), 1);
      |                                            ^~~

• Subtask 1: 60 / 100