Submission #424842

#	Time	Username	Problem	Language	Result	Execution time	Memory
424842		blue	Harbingers (CEOI09_harbingers)	C++17	20 / 100	1093 ms	18336 KiB

harbingers

#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 (stderr)

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 / 100