oj.uz

Submission #869133

# Submission time Handle Problem Language Result Execution time Memory
869133 2023-11-03T09:47:45 Z sleepntsheep Harbingers (CEOI09_harbingers) C++17
0 / 100
 41 ms 17900 KB 
#include <cstdio>
#include <stack>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 100005
#define ALL(x) x.begin(), x.end()

struct line
{
    ll m, c;
    line(ll m, ll c) : m(m), c(c) {}
    line() : m(0), c(0) {}
    inline ll operator[](ll x) { return m*x+c; }
    inline ll intersect(line &l) { return (ll)(c-l.c)/(l.m-m); }
};

int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];
line cht[N]; int sz;

inline int add(line k)
{
    int l = 1, r = sz - 1, z = sz;
    for (; l <= r;)
    {
        int m = (l+r)/2;
        if (cht[m].intersect(cht[m-1]) > cht[m-1].intersect(k)) z = m, l = m + 1;
        else r = m - 1;
    }
    if (z == sz) ++sz;
    return z;
}

inline ll qry(ll x)
{
    int l = 0, r = sz - 2, z = sz - 1;
    for (;l <= r;)
    {
        int m = (l+r)/2;
        if (cht[m].intersect(cht[m+1]) < x) l=m+1;
        else r=m-1, z = m;
    }
    return cht[z][x];
}

void dfs(int u, int p)
{
    int psz = sz;
    dp[u] = s[u] + 1ll*v[u]*rt[u] - qry(v[u]);
    dp[1] = 0;
    int at = add(line{rt[u], -dp[u]});
    line overwrote = cht[at];
    cht[at] = line{rt[u], -dp[u]};
    for (auto [w, v] : g[u]) if (v != p) rt[v] = rt[u] + w, dfs(v, u);
    sz = psz;
    cht[at] = overwrote;
}

int main()
{
    cht[sz++] = {0, 0};
    ShinLena;
    cin >> n;
    for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
    dfs(1, 1);
    for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9308 KB Execution killed with signal 8
2 Runtime error 5 ms 9308 KB Execution killed with signal 8
3 Runtime error 22 ms 12352 KB Execution killed with signal 8
4 Runtime error 28 ms 13908 KB Execution killed with signal 8
5 Runtime error 34 ms 15444 KB Execution killed with signal 8
6 Runtime error 39 ms 17092 KB Execution killed with signal 8
7 Runtime error 31 ms 14824 KB Execution killed with signal 8
8 Runtime error 41 ms 17356 KB Execution killed with signal 8
9 Runtime error 41 ms 17900 KB Execution killed with signal 8
10 Runtime error 41 ms 17748 KB Execution killed with signal 8