Submission #1164932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164932		trufanov.p	Harbingers (CEOI09_harbingers)	C++20	100 / 100	82 ms	23108 KiB

harbingers

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <numeric>
#include <random>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <string>
#include <array>
#include <unordered_set>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <time.h>
#include <stack>
#include <deque>

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;

struct Line {
    ll k, b;
    Line(ll k, ll b) :k(k), b(b) {}
    inline ll eval(ll x) {
        return k * x + b;
    }
};

int n;
vector<vector<pair<int, int>>> gr;
vector<ll> dp;
vector<ll> s, vel;

inline double cross(const Line& a, const Line& b) {
    return (b.b - a.b) * 1.0 / (a.k - b.k);
}

vector<Line> cht;
vector<double> pts;

void dfs(int v, int it = 0, int d = 0, int p = -1) {
    if (p != -1) {
        int pos = upper_bound(pts.begin(), pts.begin() + it, vel[v]) - pts.begin() - 1;
        dp[v] = s[v] + cht[pos].eval(vel[v]) + vel[v] * d;
    }
    Line ln(-d, dp[v]);
    bool removed = false;
    int old_it = it;
    Line sv(0, 0);
    double sv_pt = 0;
    if (cht.empty() || (it == cht.size() && cross(cht.back(), ln) > pts.back())) {
        if (cht.empty()) {
            pts.push_back(-1e18);
        } else {
            pts.push_back(cross(cht.back(), ln));
        }
        cht.push_back(ln);
        it++;
    } else {
        removed = true;
        if (cross(cht[it - 1], ln) > pts[it - 1]) {
            sv = cht[it];
            sv_pt = pts[it];
            cht[it] = ln;
            pts[it] = cross(cht[it - 1], ln);
            it++;
        } else {
            int l = 0, r = it - 1;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (cross(ln, cht[m - 1]) <= pts[m]) {
                    r = m;
                } else {
                    l = m;
                }
            }
            sv = cht[r];
            sv_pt = pts[r];
            cht[r] = ln;
            pts[r] = cross(ln, cht[r - 1]);
            it = r + 1;
        }
    }
    for (auto& [u, len] : gr[v]) {
        if (u != p) {
            dfs(u, it, d + len, v);
        }
    }
    if (removed) {
        cht[it - 1] = sv;
        pts[it - 1] = sv_pt;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    gr.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        u--, v--;
        gr[u].push_back({ v, d });
        gr[v].push_back({ u, d });
    }
    s.resize(n);
    vel.resize(n);
    for (int i = 1; i < n; ++i) {
        cin >> s[i] >> vel[i];
    }
    dp.resize(n);
    dfs(0);
    for (int i = 1; i < n; ++i) {
        cout << dp[i] << ' ';
    }
}

• Subtask 1: 100 / 100