제출 #1270922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270922		rayan_bd	Harbingers (CEOI09_harbingers)	C++20	10 / 100	25 ms	34372 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2505;
#define int long long
const int inf = 2e18;
vector<pair<int, int>> adj[mxN];
vector<int> nodes[mxN];
int pref[mxN], depth[mxN], dp[mxN][mxN], s[mxN], k[mxN], ans[mxN];
void dfs(int u = 1, int par = 0){
    dp[u][0] = u;
    if(u != 1){
        depth[u] = depth[par] + 1;
        for(int i = 1; i <= depth[u]; ++i){
            dp[u][i] = dp[par][i - 1];
        }
    }
    nodes[depth[u]].push_back(u);
    for(auto it : adj[u]){
        if(it.first ^ par){
            pref[it.first] = pref[u] + it.second;
            dfs(it.first, u);
        }
    }
}
void test_case(){
    int n, u, v, d;
    cin >> n;
    for(int i = 1; i <= n - 1; ++i){
        cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    for(int i = 2; i <= n; ++i){
        cin >> s[i] >> k[i];
    }
    dfs();
    for(int i = 2; i <= n; ++i) ans[i] = inf;
    ans[1] = 0;
    auto cost = [&](int x, int y) -> int {
        if(x == y){
            return s[x] + (pref[x] * k[x]);
        }else{
            return s[x] + ((pref[x] - pref[y]) * k[x]);
        }
    };
    for(int i = 1; i <= n; ++i){
        for(auto it : nodes[i]){
            for(int j = 0; j <= n; ++j){
                if(dp[it][j] == 0) break;
                ans[it] = min(ans[it], ans[dp[it][j]] + cost(it, dp[it][j]));
            }
        }
    }
    for(int i = 2; i <= n; ++i) cout << ans[i] << " ";
    cout << "\n";
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    test_case();
    return 0;
}

• Subtask 1: 10 / 100