Submission #1266324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266324		_ll	Harbingers (CEOI09_harbingers)	C++20	50 / 100	1096 ms	34200 KiB

harbingers

#include<bits/stdc++.h>// persistent stack - binary lifting - convex hull trick (Obra de arteeeeee)
using namespace std;
typedef long long ll;
typedef double ld;
ll const sz = 1e5, 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 pro convex hull
        array<int, pd> bf = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};// binary lifting para achar a reta que maximiza
};
vector<no> ps;

ld xinter(array<ld, 2> a, array<ld, 2> b){ // pelas ruas serem não negativas nunca dividirá por zero
        return (b[1] - a[1]) / (a[0] - b[0]); // x da interseção das retas 
}

bool 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){ // adiciona at a persistent queue como filho do indice ip
        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)) // se a reta "a" cobre a reta pai remove o pai
                at = ps[at].bf[0]; // indica de onde eu continuo a persistent stack
        if(at > 0){
                no aux = ps[at];
                aux.inf[2] = xinter({ps[at].inf[0], ps[at].inf[1]}, a); // preciso criar um nó novo
                at = ps.size();
                ps.push_back(aux); // crio um nó cópia do pai, para mudar o termino dele
        }
        no f;
        f.inf = {a[0], a[1],  (ld) oo};
        f.bf[0] = at;
        for(ll i = 1; i < pd; i++)
                f.bf[i] = ps[f.bf[i - 1]].bf[i - 1];
        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;
        z.inf = {1, 0,  (ld) oo};
        ps.push_back(ini);
        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: 50 / 100