oj.uz

Submission #579902

# Submission time Handle Problem Language Result Execution time Memory
579902 2022-06-20T08:42:10 Z leeh18 Harbingers (CEOI09_harbingers) C++17
0 / 100
 66 ms 23124 KB 
#include <bits/stdc++.h>

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

using namespace std;
using ll = long long;

struct line {
    ll a, b;
    line(ll a_, ll b_) : a(a_), b(b_) {}
    line() : a(0LL), b(0LL) {}
    ll operator()(ll x) const {
        return a * x + b;
    }
};

ll floor_div(ll a, ll b) {
    return a / b - ((a ^ b) < 0 && a % b);
}

ll intersect(const line& l1, const line& l2) {
    return floor_div(l2.b - l1.b, l1.a - l2.a);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
    int N;
    cin >> N;
    vector<vector<pair<int, ll>>> adj(N+1);
    for (int i = 0; i < N-1; i++) {
        int U, V, D;
        cin >> U >> V >> D;
        adj[U].emplace_back(V, (ll)D);
        adj[V].emplace_back(U, (ll)D);
    }
    vector<ll> S(N+1), V(N+1);
    for (int i = 2; i <= N; i++) {
        cin >> S[i] >> V[i];
    }
    vector<ll> dp(N+1);
    vector<line> st(1);
    auto dfs = y_combinator([&](auto self, int u, int parent, ll dist) -> void {
        int lo = 0, hi = (int)st.size() - 1;
        ll x = V[u];
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (intersect(st[mid-1], st[mid]) < x) lo = mid;
            else hi = mid - 1;
        }
        dp[u] = S[u] + V[u] * dist - st[lo](x);
        vector<line> tmp;
        line cur(dist, -dp[u]);
        while ((int)st.size() > 1 && intersect(cur, st[(int)st.size()-1]) <= intersect(st[(int)st.size()-1], st[(int)st.size()-2])) {
            tmp.push_back(st.back());
            st.pop_back();
        }
        st.push_back(cur);
        for (auto [v, w] : adj[u]) {
            if (v != parent) {
                self(v, u, dist+w);
            }
        }
        st.pop_back();
        for (int i = (int)tmp.size()-1; i >= 0; i--) {
            st.push_back(tmp[i]);
        }
    });
    dfs(1, 1, 0);
    for (int i = 2; i <= N; i++) {
        cout << dp[i] << " \n"[i == N];
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 8
2 Runtime error 2 ms 980 KB Execution killed with signal 8
3 Runtime error 28 ms 9804 KB Execution killed with signal 8
4 Runtime error 43 ms 14024 KB Execution killed with signal 8
5 Runtime error 50 ms 18760 KB Execution killed with signal 8
6 Runtime error 66 ms 23124 KB Execution killed with signal 8
7 Runtime error 41 ms 15632 KB Execution killed with signal 8
8 Runtime error 63 ms 22996 KB Execution killed with signal 8
9 Runtime error 62 ms 22692 KB Execution killed with signal 8
10 Runtime error 60 ms 21828 KB Execution killed with signal 8