Submission #773964

#	Time	Username	Problem	Language	Result	Execution time	Memory
773964		MilosMilutinovic	Harbingers (CEOI09_harbingers)	C++14	0 / 100	98 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int M = 30 * N;
const int inf = 1e9;
int n, s[N], t[N];
ll dp[N], dep[N];
vector<pair<int, int>> g[N];
struct Line {
    ll k, n;
    Line() { k = 0; n = 1e18; }
    Line(ll _k, ll _n) : k(_k), n(_n) {}
    ll eval(ll x) { return k * x + n; }
} st[M];
int root[N], ls[M], rs[M], tsz;
void modify(int& v, int pv, int l, int r, Line ln) {
    v = ++tsz;
    ls[v] = ls[pv];
    rs[v] = rs[pv];
    st[v] = st[pv];
    int mid = l + r >> 1;
    if (ln.eval(mid) < st[v].eval(mid)) {
        swap(st[v], ln);
    }
    if (l == r) return;
    if (ln.eval(l) < st[v].eval(l)) {
        modify(ls[v], ls[pv], l, mid, ln);
    } else {
        modify(rs[v], rs[pv], mid + 1, r, ln);
    }
}
ll query(int v, int l, int r, int p) {
    if (l == r) {
        return st[v].eval(p);
    }
    int mid = l + r >> 1;
    ll res = st[v].eval(p);
    if (p <= mid) {
        res = min(res, query(ls[v], l, mid, p));
    } else {
        res = min(res, query(rs[v], mid + 1, r, p));
    }
    return res;
}
void dfs(int v, int pv) {
    // (dep[x] - dep[y]) * speed[x] + dp[y] + time[x]
    if (v != 1) {
        dp[v] = query(root[pv], 1, inf, s[v]) + dep[v] * s[v] + t[v];
    }
    modify(root[v], root[pv], 1, inf, Line(-dep[v], dp[v]));
    for (auto& e : g[v]) {
        int u = e.first;
        int w = e.second;
        if (u == pv) {
            continue;
        }
        dep[u] = dep[v] + w;
        dfs(u, v);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &t[i], &s[i]);
    }
    dfs(1, 1);
    for (int i = 2; i <= n; i++) {
        printf("%lld ", dp[i]);
    }
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void modify(int&, int, int, int, Line)':
harbingers.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = l + r >> 1;
      |               ~~^~~
harbingers.cpp: In function 'long long int query(int, int, int, int)':
harbingers.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
harbingers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d%d%d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d", &t[i], &s[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100