Submission #1310495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310495		buzdi	Harbingers (CEOI09_harbingers)	C++17	20 / 100	1097 ms	9996 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 1e5;
const ll INF = 1e18;

int n;
ll dp[NMAX + 1];
ll sp[NMAX + 1];
int st[NMAX + 1], v[NMAX + 1];
vector<pair<int, int>> g[NMAX + 1];
int parent[NMAX + 1];

ll get_dp(int node) {
    ll mini = INF;
    int dad = parent[node];
    while(dad != 0) {
        mini = min(mini, dp[dad] - sp[dad] * v[node]);
        dad = parent[dad];
    }
    return st[node] + sp[node] * v[node] + mini;
}

void DFS(int node, int dad = 0) {
    parent[node] = dad;
    if(node != 1) {
        dp[node] = get_dp(node);
    }
    for(auto [next_node, c] : g[node]) {
        if(next_node != dad) {
            sp[next_node] = sp[node] + c;
            DFS(next_node, node);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    for(int i = 2; i <= n; i++) {
        cin >> st[i] >> v[i];
    }

    DFS(1);
    for(int i = 2; i <= n; i++) {
        cout << dp[i] << ' ';
    }
    return 0;
}

• Subtask 1: 20 / 100