Submission #409255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409255	2021-05-20T12:49:13 Z	Falcon	Harbingers (CEOI09_harbingers)	C++17	30 / 100	1000 ms	65544 KB

harbingers

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }

#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

// From http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
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 point = complex<long long>;
namespace CHT {
    vector<point> v;
    stack<stack<point>> u;

    long long dot(point p, point q) {
        return real(conj(p) * q);
    }

    long long cross(point p, point q) {
        return imag(conj(p) * q);
    }

    void add_line(point p) {
        u.push({});
        while(v.size() > 1) {
            point a{v[int(v.size()) - 1]}, b{v[int(v.size()) -2]};
            if(cross(b - a, p - a) <= 0) v.pop_back(), u.top().push(a);
            else break;
        }
        v.push_back(p);
    }

    void undo_add() {
        v.pop_back();
        while(!u.top().empty()) v.push_back(u.top().top()), u.top().pop();
        u.pop();
    }

    long long get_best(long long x) {
        int t{};
        point p(x, 1);
        for(int k{1 << __lg(int(v.size()))}; k > 0; k >>= 1)
            if(t + k < int(v.size()) && dot(v[t + k] - v[t + k - 1], p) >= 0)
                t += k;
        return dot(p, v[t]);
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vector<vector<pair<int, long long>>> adj(n);
    rep(i, n - 1) {
        int u, v, d; cin >> u >> v >> d; --u, --v;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    vector<int> s(n), v(n);
    rep1(i, n - 1) cin >> s[i] >> v[i];

    vector<long long> ans(n);
    y_combinator([&](auto dfs, int u, long long d, int pre) -> void {
        if(u != 0) 
            ans[u] = v[u] * d + s[u] -CHT::get_best(v[u]);
        CHT::add_line(point(d, -ans[u]));

        for(auto [x, w]: adj[u]) if(x != pre)
            dfs(x, d + w, u);

        CHT::undo_add();
    })(0, 0, -1);

    rep1(i, n - 1) cout << ans[i] << ' ';
    cout << '\n';
    
    #ifdef DEBUG
    dbg::dout << "\nExecution time: "
              << clock() * 1000 / CLOCKS_PER_SEC 
              << "ms" << endl;
    #endif
    return 0;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	5 ms	2380 KB	Output is correct
3	Runtime error	75 ms	34752 KB	Memory limit exceeded
4	Runtime error	108 ms	51508 KB	Memory limit exceeded
5	Runtime error	140 ms	65544 KB	Execution killed with signal 9
6	Runtime error	138 ms	65540 KB	Execution killed with signal 9
7	Correct	99 ms	27752 KB	Output is correct
8	Execution timed out	1090 ms	42036 KB	Time limit exceeded
9	Execution timed out	1085 ms	26292 KB	Time limit exceeded
10	Execution timed out	1067 ms	48628 KB	Time limit exceeded