Submission #132504

#	Time	Username	Problem	Language	Result	Execution time	Memory
132504		lyc	Harbingers (CEOI09_harbingers)	C++14	90 / 100	190 ms	24696 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
 
const int MAXN = 1e5+5;
const int lgN = 17;
 
int N;
vector<ii> al[MAXN];
int S[MAXN], V[MAXN];
int p[MAXN];
int d[MAXN];
ll r[MAXN];
 
struct Line { int m; ll b; ll f(int x) { return (ll)m*x + b; } };
struct Hull {
    Line v[MAXN];
    int p[MAXN][lgN], vp;

    Hull() { memset(p, -1, sizeof p); vp = 1; }

    bool bad(Line a, Line b, Line c) {
        return ((ll)c.b - b.b) * ((ll)a.m - b.m) <= ((ll)b.b - a.b) * ((ll)b.m - c.m); }
    
    int add(Line l, int idx) {
        RFOR(k,lgN-1,0) if (p[idx][k] != -1 and p[p[idx][k]][0] != -1 
                and bad(v[p[p[idx][k]][0]], v[p[idx][k]], l))
            idx = p[idx][k];
        if (p[idx][0] != -1 and bad(v[p[idx][0]], v[idx], l)) idx = p[idx][0];
        v[vp] = l;
        p[vp][0] = idx;
        FOR(k,1,lgN-1) p[vp][k] = (p[vp][k-1] == -1 ? -1 : p[p[vp][k-1]][k-1]);
        return vp++;
    }

    ll query(int x, int idx) {
        RFOR(k,lgN-1,0) if (p[idx][k] != -1 and p[p[idx][k]][0] != -1
                and v[p[p[idx][k]][0]].f(x) <= v[p[idx][k]].f(x))
            idx = p[idx][k];
        if (p[idx][0] != -1 and v[p[idx][0]].f(x) <= v[idx].f(x)) idx = p[idx][0];
        return v[idx].f(x);
    }
} ch;
 
void dfs(int u, int p, int pidx) {
	r[u] = (ll)S[u] + (ll)V[u]*d[u];
	//cout << u << " " << p[u] << endl;
	//for (int v = p[u]; v != 0; v = p[v]) r[u] = min(r[u], (ll)S[u] + (ll)V[u]*(d[u]-d[v]) + r[v]);
	if (u > 1) r[u] = min(r[u], ch.query(V[u], pidx) + (ll)S[u] + (ll)V[u]*d[u]);
	int idx = ch.add({ -d[u], r[u] }, pidx);
	for (auto v : al[u]) if (v.fi != p) {
		d[v.fi] = d[u] + v.sc;
		dfs(v.fi, u, idx);
	}
}
 
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	cin >> N;
	FOR(i,1,N-1){
		int u, v, d; cin >> u >> v >> d;
		al[u].emplace_back(v, d);
		al[v].emplace_back(u, d);
	}
 
	FOR(i,2,N){ cin >> S[i] >> V[i]; }
	dfs(1,0,0);
 
	FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' ');
}
 

• Subtask 1: 90 / 100