Submission #859573

#	Time	Username	Problem	Language	Result	Execution time	Memory
859573		sleepntsheep	Harbingers (CEOI09_harbingers)	C++17	20 / 100	49 ms	21076 KiB

harbingers

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <functional> 
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define ALL(x) x.begin(), x.end()

int n, prep[1<<19], vel[1<<19];
vector<pair<int, int>> g[1<<19];

/*
 * dp[i] = cost from i to 1
 *
 * dp[i] = min p (dp[p] + distance(i, p) + start[i])
 *
 */

int sub1()
{
    const int N = 2586;
    ll dp[N]{0}, tin[N], tout[N], timer = 1, rd[N];
    function<void(int, int, int)> dfs = [&](int u, int p, ll d) {
        tin[u] = timer++;
        rd[u] = d;
        for (auto [w, v] : g[u]) if (v != p) dfs(v, u, d+w);
        tout[u] = timer - 1;
    };
    dfs(1, 1, 0);
    memset(dp, 63, sizeof dp);
    dp[1] = 0;
    function<void(int, int)> dfs1 = [&](int u, int p) {
        for (int a = 1; a <= n; ++a)
            if (tin[a] <= tin[u] && tout[u] <= tout[a]) dp[u] = min(dp[u], dp[a] + prep[u] + vel[u] * (rd[u] - rd[a]));
        for (auto [w, v] : g[u]) if (v != p) dfs1(v, u);
    };
    dfs1(1, 1);
    for (int i = 2; i <= n; ++i) printf("%lld ", dp[i]);
    return 0;
}

int main()
{
    scanf("%d", &n);
    for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 2; i <= n; ++i) scanf("%d%d", prep+i, vel+i);
    if (n <= 2500) return sub1();

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
harbingers.cpp:54:47: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), g[u].emplace_back(w, v), g[v].emplace_back(w, u);
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:55:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     for (int i = 2; i <= n; ++i) scanf("%d%d", prep+i, vel+i);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100