Submission #1266750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266750		_ll	Harbingers (CEOI09_harbingers)	C++20	40 / 100	1065 ms	18760 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef float ld;
vector<array<ll, 2>> g[100000];
array<ll, 2> ps[100000], all[100000];
ll oo = 1e12, re[100000];

ld xinter(array<ll, 2> a, array<ll, 2> b){
        array<ld, 2> at = {(ld) a[0], (ld) a[1]}, bt = {(ld) b[0], (ld) b[1]};
        return (bt[1] - at[1]) / (at[0] - bt[0]);
}

ld chinter(ll id, ll i){
    if(i >= id - 1) return oo; // oo é a interseção
    return xinter(ps[i], ps[i + 1]); 
}

ll vl(ll id, ll x){
        ll l = 1, r = id, vl = 1e12;
        while(l <= r){
                ll m = (l + r) / 2;
                if(x <= chinter(id, m)) r = m - 1;
                else                    l = m + 1;
        }
        return ps[l][0] * x + ps[l][1];
}

array<ll, 2> ins(ll &ind, array<ll, 2> at){
        while(ind > 2 && xinter(ps[ind - 2], at) <= xinter(ps[ind - 2], ps[ind - 1]))
                --ind;
        auto ax = ps[ind];
        ps[ind] = at;
        return ax;
}

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;
        re[at] = res + c;
        auto aux = ins(ia, {-del, res + c});// o unico nó que editei
        for(auto [i, j] : g[at]) if(i != p)
                dfs(at, i, del + j, ia + 1);
        ps[ia] = aux;
}

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];
        ps[0] = {1, 0};
        dfs(-1, 0, 0, 1);
        for(ll i = 1; i < n; i++)
                cout << to_string((ll) re[i]) << " ";
        cout << "\n";
}

• Subtask 1: 40 / 100