Submission #336856

#	Time	Username	Problem	Language	Result	Execution time	Memory
336856		Vince729	Harbingers (CEOI09_harbingers)	C++11	20 / 100	1093 ms	18284 KiB

harbingers

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

typedef long long ll;

const int MAXN = 100002;
const int MOD = 1000000007;

struct path {
    int t;
    ll d;
};

int n;
vector<path> adj[MAXN];
int si[MAXN], vi[MAXN];
ll ans[MAXN];
path anc[MAXN];

void dfs1(int x, int p) {
    for (path v : adj[x]) {
        if (v.t == p) {
            anc[x] = v;
        } else {
            dfs1(v.t, x);
        }
    }
}

void dfs2(int x, int p) {
    ll dist = anc[x].d;
    int bi = p;
    ll best = si[x]+dist*vi[x]+ans[bi];
    do {
        dist += anc[bi].d;
        bi = anc[bi].t;
        best = min(best, si[x]+dist*vi[x]+ans[bi]);
    } while (bi != 1);
    ans[x] = best;
    for (path v : adj[x]) {
        if (v.t != p) dfs2(v.t, x);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v, d; cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    for (int i = 2; i <= n; i++) {
        cin >> si[i] >> vi[i];
    }
    dfs1(1, 1);
    anc[1] = {1, 0};
    dfs2(1, 1);
    for (int i = 2; i <= n; i++) cout << ans[i] << " ";
}

• Subtask 1: 20 / 100