Submission #210487

#	Time	Username	Problem	Language	Result	Execution time	Memory
210487		karma	Harbingers (CEOI09_harbingers)	C++14	80 / 100	165 ms	33912 KiB

harbingers

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
#define sz(x)       int(x.size())
//#define int         int64_t

using namespace std;

typedef pair<ll, ll> pii;
const int N = int(2e5 + 5);
const int inf = (int)1e18;

int n, p[N], u, v, w;
int id[N], big[N], sz[N], cnt, head[N];
ll f[N], d[N], pi[N], qi[N];
vector<pii> adj[N];

ll operator*(const pii& x, const pii& y) {return x.fi * y.se - y.fi * x.se;}
pii operator-(const pii& x, const pii& y) {return {x.fi - y.fi, x.se - y.se};}
ll ccw(const pii& a, const pii& b, const pii& c) {return (c - b) * (b - a);}
struct TConvex {
    vector<pii> hull; int sz, low, high, mid; ll res;
    TConvex() {hull.clear(), sz = 0;}
    void push(const pii& p) {
        for(; sz > 1 && ccw(hull[sz - 2], hull[sz - 1], p) <= 0; hull.pop_back(), --sz);
        hull.pb(p); ++sz;
    }
    ll val(int i, ll x) {return (i < sz && i >= 0)? hull[i].fi * x + hull[i].se: inf;}
    ll get(ll x) {
        if(hull.empty()) return inf;
        low = 0, high = sz - 1;
        while(low <= high) {
            mid = (low + high) >> 1;
            if(val(mid, x) >= val(mid + 1, x)) low = mid + 1;
            else high = mid - 1;
        }
        return min(val(low, x), val(high, x));
    }
} cvh[N];

void dfs(int u) {
    sz[u] = 1; big[u] = -1;
    for(auto& v: adj[u]) {
        if(v.fi == p[u]) swap(v, adj[u].back());
        if(v.fi == p[u]) continue;
        d[v.fi] = d[u] + v.se;
        p[v.fi] = u; dfs(v.fi);
        if(big[u] == -1 || sz[big[u]] < sz[v.fi]) big[u] = v.fi;
        sz[u] += sz[v.fi];
    }
    if(u != 1) adj[u].pop_back();
}

ll dp(int st) {
    if(st == 1) return 0;
    int cur = st, idu; ll res = inf;
    while(cur) {
        idu = id[cur];
        res = min(res, cvh[idu].get(pi[st]));
        cur = p[head[idu]];
    }
    return res + 1ll * d[st] * pi[st] + qi[st];
}

void hld(int u) {
    if(head[id[u]] == 0) head[id[u]] = u;
    f[u] = dp(u);
    cvh[id[u]].push({-d[u], f[u]});
    for(auto v: adj[u]) {
        if(v.fi == big[u]) continue;
        id[v.fi] = ++cnt;
        hld(v.fi);
    }
    if(big[u] == -1) return;
    id[big[u]] = id[u];
    hld(big[u]);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        adj[u].pb(v, w);
        adj[v].pb(u, w);
    }
    for(int i = 2; i <= n; ++i) cin >> qi[i] >> pi[i];
    dfs(1); hld(1);
    for(int i = 2; i <= n; ++i) cout << f[i] << ' ';
}

Compilation message (stderr)

harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100