oj.uz

Submission #641160

# Submission time Handle Problem Language Result Execution time Memory
641160 2022-09-16T06:23:27 Z sumit_kk10 Harbingers (CEOI09_harbingers) C++17
20 / 100
 1000 ms 38988 KB 
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
vector<pair<int, int> > g[N];
int n, par[N], dis[N], dp[N], s[N], d[N];
bool vis[N];

void dfs(int node, int p, int sum){
    dis[node] = sum;
    par[node] = p;
    for(auto k : g[node]){
        if(k.F == p) continue;
        dfs(k.F, node, sum + k.S);
    }
}

void bfs(int node){
    queue<int> q;
    q.push(node);
    vis[node] = true;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node != 1){
            // calculate dp[node]
            int cur = par[node];
            dp[node] = LLONG_MAX;
            while(cur != 0){
                int x = (dis[node] - dis[cur]) * d[node] + s[node];
                dp[node] = min(dp[node], x + dp[cur]);
                cur = par[cur];
            }
        }
        for(auto k : g[node]){
            if(!vis[k.F]){
                vis[k.F] = true;
                q.push({k.F});
            }
        }
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    for(int i = 1; i < n; ++i)
        cin >> s[i + 1] >> d[i + 1];
    dfs(1, 0, 0);
    bfs(1);
    for(int i = 2; i <= n; ++i)
        cout << dp[i] << " ";
}

int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 31 ms 24236 KB Output is correct
3 Execution timed out 1083 ms 30152 KB Time limit exceeded
4 Execution timed out 1083 ms 32924 KB Time limit exceeded
5 Execution timed out 1082 ms 36204 KB Time limit exceeded
6 Execution timed out 1067 ms 38988 KB Time limit exceeded
7 Execution timed out 1081 ms 32720 KB Time limit exceeded
8 Execution timed out 1081 ms 36928 KB Time limit exceeded
9 Execution timed out 1081 ms 37364 KB Time limit exceeded
10 Execution timed out 1086 ms 36512 KB Time limit exceeded