제출 #1265272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265272		_ll	Harbingers (CEOI09_harbingers)	C++20	40 / 100	69 ms	31880 KiB

harbingers

#include<bits/stdc++.h>// persistent stack - binary lifting - convex hull trick (Obra de arteeeeee)
using namespace std;
typedef long long ll;
typedef long double ld;
ll const sz = 6e4, pd = 16;
vector<array<int, 2>> g[sz]; 
array<int, 2> all[sz];
ll oo = 1e12, re[sz];
struct no {
        array<ld, 3> inf = {1, (ld) oo, -1}; // coeficientes e intersecção
        array<int, pd> bf = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};// binary lifting
        vector<int> f;     // filhos
};
vector<no> ps;

ld xinter(array<ld, 2> a, array<ld, 2> b){
        if(b[0] == a[0]) return -1; // pelas ruas serem não negativas isso nunca acontece (o multiplicador sempre diminui)
        ld x = (b[1] - a[1]) / (a[0] - b[0]);
        return x;
}

ll men(array<ld, 3> a, array<ld, 2> b){ // me diz se é menor
        return(xinter({a[0], a[1]}, b) <= a[2]);
}

void nps(ll &ip, no &at){ // vou criar um ip auxiliar pois vou mudar as informações
    at.bf[0] = ip;
    for(ll i = 1; i < pd; i++){
        at.bf[i] = ps[at.bf[i - 1]].bf[i - 1];
    }
    ps[ip].f.push_back(ps.size());
    ip = ps.size();
    ps.push_back(at);
}

void ins(ll &at, array<ld, 2> a){
        while(ps[at].bf[0] > 0 && men(ps[ps[at].bf[0]].inf, a)) // olho o pai do ultimo se o ponto de termino for maior 
                at = ps[at].bf[0]; // que o ponto de intersecção sei q o atual continua o do pai
        if(at > 0){
            no aux = ps[at];
            aux.inf[2] = xinter({ps[at].inf[0], ps[at].inf[1]}, a);
            ps[aux.bf[0]].f.push_back(ps.size());
            at = ps.size();
            ps.push_back(aux);
        }
        no f;
        f.inf = {a[0], a[1],  (ld) oo};
        nps(at, f); // arruma o binarylifting, coloca ele na pilha e muda o at
} // agora falta o consulta na posição x a partir de um indice atual da pilha

ll vl(ll iat, ll x){
    for(ll i = pd - 1; i >= 0; i--) if(ps[ps[iat].bf[i]].inf[2] >= x)
        iat = ps[iat].bf[i];
    return (ll) (ps[iat].inf[0] * x + ps[iat].inf[1]); // acha o minimo em um x usando a queue com iat no topo
}

void dfs(ll p, ll at, ll del, ll ia){
        ll res = vl(ia, all[at][1]), c = all[at][0] + all[at][1] * del; // olha a beleza disso
        re[at] = res + c;
        ins(ia, {(ld) -del, (ld) res + c});
        for(auto [i, j] : g[at]) if(i != p)
                dfs(at, i, del + j, ia);// tenho q somar isso nas arestas
}

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

        ll n; cin >> n;
        for(int i = 1, a, b, c; i < n; i++){
                cin >> a >> b >> c; a--, b--;
                g[a].push_back({b, c});
                g[b].push_back({a, c});
        }
        for(ll i = 1; i < n; i++)
                cin >> all[i][0] >> all[i][1];
        no ini, z;
        ps.push_back(ini);
        z.inf = {0, 0,  (ld) oo};
        ll at = 0;
        nps(at, z);
        dfs(-1, 0, 0, at);
        for(ll i = 1; i < n; i++)
                cout << to_string((ll) re[i]) << " ";
        cout << "\n";
} 

• Subtask 1: 40 / 100