Submission #131644

#	Time	Username	Problem	Language	Result	Execution time	Memory
131644		lyc	Harbingers (CEOI09_harbingers)	C++14	80 / 100	162 ms	23012 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; } };
const Line END = {(int)-2e9, (ll)-3e18};
struct Op { Line o, n; };
struct Hull {
	Line v[MAXN]; int vp = 0;
    int p[MAXN][lgN];
     
    Hull() { memset(p, -1, sizeof p); }
 
	int add(Line l, int ep) {
        v[vp] = l;
        int u = ep;
        if (u != -1 && p[u][0] != -1 && ((ll)l.b-v[u].b)*((ll)v[p[u][0]].m-v[u].m) <= ((ll)v[u].b-v[p[u][0]].b)*((ll)v[u].m-l.m)) {
            RFOR(k,lgN-1,0) if (p[u][k] != -1 && (p[p[u][k]][0] != -1 && (((ll)l.b-v[p[u][k]].b)*((ll)v[p[p[u][k]][0]].m-v[p[u][k]].m) <= ((ll)v[p[u][k]].b-v[p[p[u][k]][0]].b)*((ll)v[p[u][k]].m-l.m)))) u = p[u][k];
            u = p[u][0];
        }
        //cout << "ADD LINE " << l.m << " " << l.b << " TO " << u << endl;
        //cout << "\t\t"; FOR(i,0,vp-1) { cout << "(" << v[i].m << "," << v[i].b << ") "; } cout << endl;

        p[vp][0] = u;
        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 ep) {
        int u = ep;
        //cout << " EPPP " << p[u][0] << " " << p[p[u][0]][0] << endl;
        if (p[u][0] != -1 && v[p[u][0]].f(x) <= v[u].f(x)) {
            RFOR(k,lgN-1,0) if (p[u][k] != -1 && (p[p[u][k]][0] != -1 && (v[p[p[u][k]][0]].f(x) <= v[p[u][k]].f(x)))) { u = p[u][k]; }
            //cout << "QUERY x " << x << " AT " << u << " ep " << ep << endl;
            u = p[u][0];
        }
        assert(u != -1);
        //cout << "QUERY x " << x << " AT " << u << " ep " << ep << endl;
        //cout << "\t\t"; FOR(i,0,vp-1) { cout << "(" << v[i].m << "," << v[i].b << ") "; } cout << endl;
        return v[u].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,-1);
 
	FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' ');
}
 

• Subtask 1: 80 / 100