oj.uz

Submission #491458

# Submission time Handle Problem Language Result Execution time Memory
491458 2021-12-02T14:58:55 Z blue Harbingers (CEOI09_harbingers) C++17
20 / 100
 1000 ms 19036 KB 
#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define pb push_back

const int maxN = 100'000;

ll INF = 2'000'000'001;

vector<pair<int, ll>> edge[1+maxN];

vll S(1+maxN), V(1+maxN);
vi P(1+maxN);
vll D(1+maxN, 0);

vi ord;

void dfs(int u, int p)
{
    ord.push_back(u);
    P[u] = p;
    for(auto x: edge[u])
    {
        int v = x.first;
        ll d = x.second;
        if(v == p) continue;
        D[v] = D[u] + d;
        dfs(v, u);
    }
}

int main()
{
    int N;
    cin >> N;

    for(int i = 1; i <= N-1; i++)
    {
        int u, v;
        ll d;
        cin >> u >> v >> d;

        edge[u].pb({v, d});
        edge[v].pb({u, d});
    }

    for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];

    dfs(1, 1);

    vll dp(1+N, INF);
    dp[1] = 0;
    for(int u: ord)
    {
        for(int v = P[u]; 1; v = P[v])
        {
            dp[u] = min(dp[u], S[u] + V[u]*D[u] + (-D[v] * V[u] + dp[v]));
            if(v == 1) break;
        }
    }

    for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
    cout << '\n';
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 20 ms 5868 KB Output is correct
3 Execution timed out 1062 ms 11264 KB Time limit exceeded
4 Execution timed out 1058 ms 13764 KB Time limit exceeded
5 Execution timed out 1092 ms 16576 KB Time limit exceeded
6 Execution timed out 1082 ms 19036 KB Time limit exceeded
7 Execution timed out 1092 ms 12696 KB Time limit exceeded
8 Execution timed out 1057 ms 16156 KB Time limit exceeded
9 Execution timed out 1064 ms 16948 KB Time limit exceeded
10 Execution timed out 1088 ms 16000 KB Time limit exceeded