oj.uz

Submission #424842

# Submission time Handle Problem Language Result Execution time Memory
424842 2021-06-12T10:47:32 Z blue Harbingers (CEOI09_harbingers) C++17
20 / 100
 1000 ms 18336 KB 
#include <iostream>
#include <vector>
using namespace std;

const long long INF = 1'000'000'000'000'000'000LL;
const int maxN = 100000;
int N;
vector<int> edge[maxN+1];
vector<long long> wt[maxN+1];
long long S[maxN+1], V[maxN+1];

vector<int> parent(maxN+1, -1);
vector<long long> dist1(maxN+1);
vector<long long> dp(maxN+1, INF);

void dfs(int u)
{
    // cerr << "dfs " << u << '\n';
    for(int v = parent[u]; v != 0; v = parent[v])
    {
        // cerr << u << ' ' << v << '\n';
        dp[u] = min(dp[u], S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v]);
    }

    for(int e = 0; e < edge[u].size(); e++)
    {
        int v = edge[u][e];
        int d = wt[u][e];

        if(parent[v] != -1) continue;

        parent[v] = u;
        dist1[v] = dist1[u] + d;

        dfs(v);
    }
}

int main()
{
    cin >> N;

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

        edge[u].push_back(v);
        wt[u].push_back(d);

        edge[v].push_back(u);
        wt[v].push_back(d);
    }

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

    parent[1] = 0;
    dist1[1] = 0;
    dp[1] = 0;
    S[1] = V[1] = 0;

    cerr << "check\n";

    dfs(1);

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

Compilation message

harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int e = 0; e < edge[u].size(); e++)
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6972 KB Output is correct
2 Correct 24 ms 7252 KB Output is correct
3 Execution timed out 1088 ms 11972 KB Time limit exceeded
4 Execution timed out 1090 ms 13872 KB Time limit exceeded
5 Execution timed out 1087 ms 16056 KB Time limit exceeded
6 Execution timed out 1074 ms 17788 KB Time limit exceeded
7 Execution timed out 1090 ms 14672 KB Time limit exceeded
8 Execution timed out 1093 ms 18148 KB Time limit exceeded
9 Execution timed out 1090 ms 18336 KB Time limit exceeded
10 Execution timed out 1070 ms 17860 KB Time limit exceeded