Submission #1196727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196727		Ghulam_Junaid	Harbingers (CEOI09_harbingers)	C++20	20 / 100	1095 ms	13840 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

typedef long long ll;
typedef pair<ll, ll> pii;

const ll N = 1e5 + 10;
ll n;
ll s[N], req[N], d[N], dp[N];
vector<pii> g[N];
vector<ll> path;

void dfs(ll v, ll p = -1){
    path.push_back(v);
    for (auto [w, u] : g[v]){
        if (u == p) continue;
        d[u] = d[v] + w;
        
        dp[u] = 1e18;
        for (ll x : path)
            dp[u] = min(dp[u], dp[x] -s[u] * d[x] + s[u] * d[u] + req[u]);

        dfs(u, v);
    }
    path.pop_back();
}

int main(){
    cin >> n;
    for (ll i = 0; i < n - 1; i ++){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }
    for (ll i = 2; i <= n; i ++)
        cin >> req[i] >> s[i];

    dfs(1);
    for (ll i = 2; i <= n; i ++)
        cout << dp[i] << " ";
    cout << endl;
}

• Subtask 1: 20 / 100