Submission #1194533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194533		olegmak	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

using namespace std;
int best_path(int n, int k, int edges[][2], int weights[]) {
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        const auto& e = edges[i];
        g[e[0]].push_back({e[1], weights[i]});
        g[e[1]].push_back({e[0], weights[i]});
    }
    vector<long long> dist(n);
    vector<int> edge_cnt(n);
    auto dfs = [&](auto&& dfs, int u, int p) -> void {
        for (const auto [v, w] : g[u]) {
            if (v == p) {
                continue;
            }
            dist[v] = dist[u] + w;
            edge_cnt[v] = edge_cnt[u] + 1;
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 0, -1);
    constexpr int INF = numeric_limits<int>::max();
    int min_edges = INF;
    auto dfs2 = [&](auto&& dfs2, int u, int p) -> map<long long, int> {
        map<long long, int> u_stats;
        for (const auto [v, w] : g[u]) {
            if (v == p) {
                continue;
            }
            auto v_stats = dfs2(dfs2, v, u);
            if (u_stats.size() < v_stats.size()) {
                swap(u_stats, v_stats);
            }
            for (const auto v_stat : v_stats) {
                const auto l = k - v_stat.first + 2 * dist[u];
                if (auto iter = u_stats.find(l); iter != u_stats.end()) {
                    min_edges = min(min_edges, iter->second + v_stat.second - 2 * edge_cnt[u]);
                }
                auto iter2 = u_stats.insert({v_stat.first, INF}).first;
                iter2->second = min(iter2->second, v_stat.second);
            }
        }
        auto iter2 = u_stats.insert({dist[u], edge_cnt[u]}).first;
        iter2->second = min(iter2->second, edge_cnt[u]);
        const auto l = k + dist[u];
        if (auto iter = u_stats.find(l); iter != u_stats.end()) {
            min_edges = min(min_edges, iter->second - edge_cnt[u]);
        }
        return u_stats;
    };
    dfs2(dfs2, 0, -1);
    return min_edges == INF ? -1 : min_edges;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:3:19: error: 'pair' was not declared in this scope
    3 |     vector<vector<pair<int, int>>> g(n);
      |                   ^~~~
race.cpp:1:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
  +++ |+#include <utility>
    1 | using namespace std;
race.cpp:3:12: error: 'vector' was not declared in this scope
    3 |     vector<vector<pair<int, int>>> g(n);
      |            ^~~~~~
race.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using namespace std;
race.cpp:3:24: error: expected primary-expression before 'int'
    3 |     vector<vector<pair<int, int>>> g(n);
      |                        ^~~
race.cpp:6:9: error: 'g' was not declared in this scope
    6 |         g[e[0]].push_back({e[1], weights[i]});
      |         ^
race.cpp:9:12: error: expected primary-expression before 'long'
    9 |     vector<long long> dist(n);
      |            ^~~~
race.cpp:10:12: error: expected primary-expression before 'int'
   10 |     vector<int> edge_cnt(n);
      |            ^~~
race.cpp: In lambda function:
race.cpp:12:34: error: 'g' was not declared in this scope
   12 |         for (const auto [v, w] : g[u]) {
      |                                  ^
race.cpp:16:13: error: 'dist' was not declared in this scope
   16 |             dist[v] = dist[u] + w;
      |             ^~~~
race.cpp:17:13: error: 'edge_cnt' was not declared in this scope
   17 |             edge_cnt[v] = edge_cnt[u] + 1;
      |             ^~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:22:25: error: 'numeric_limits' was not declared in this scope
   22 |     constexpr int INF = numeric_limits<int>::max();
      |                         ^~~~~~~~~~~~~~
race.cpp:22:40: error: expected primary-expression before 'int'
   22 |     constexpr int INF = numeric_limits<int>::max();
      |                                        ^~~
race.cpp:24:51: error: 'map' does not name a type
   24 |     auto dfs2 = [&](auto&& dfs2, int u, int p) -> map<long long, int> {
      |                                                   ^~~
race.cpp:24:54: error: expected '{' before '<' token
   24 |     auto dfs2 = [&](auto&& dfs2, int u, int p) -> map<long long, int> {
      |                                                      ^
race.cpp:24:55: error: expected primary-expression before 'long'
   24 |     auto dfs2 = [&](auto&& dfs2, int u, int p) -> map<long long, int> {
      |                                                       ^~~~
race.cpp:12: confused by earlier errors, bailing out