Submission #1266763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266763		_ll	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	20548 KiB

harbingers

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

ld xinter(pair<ll, ll> a, pair<ll, ll> b){
        return ((ld) b.second - a.second) / ((ld) a.first - b.first);
}

ll vl(ll id, ll x){
        ll l = 1, r = id;
        while(l <= r){
                ll m = (l + r) / 2;
                if(m >= id - 1 || x <= xinter(ps[m], ps[m + 1])) r = m - 1;
                else                                             l = m + 1;
        }
        return ps[l].first * x + ps[l].second;
}

void dfs(ll p, ll at, ll del, ll id){
        ll res = vl(id, all[at].second), c = all[at].first + all[at].second * del;
        re[at] = res + c;
        while(id > 2 && xinter(ps[id - 2], {-del, res + c}) <= xinter(ps[id - 2], ps[id - 1]))
                --id;
        pair<ll, ll> aux = ps[id]; 
        ps[id] = {-del, res + c}; // inserindo no Convex Hull
        for(auto [i, j] : g[at]) if(i != p)
                dfs(at, i, del + j, id + 1);
        ps[id] = 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].first >> all[i].second;
        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: 70 / 100