Submission #792945

#	Time	Username	Problem	Language	Result	Execution time	Memory
792945		NoLove	Race (IOI11_race)	C++14	9 / 100	129 ms	48332 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
map<int, int> d[MAXN]; // d[v][k]: the minimum number of highways with length exactly k and consting node v
vector<pair<int, int>> adj[MAXN];
int res = 1e9;
void dfs(int k, int v = 0, int prev = -1) {
    for (auto[u, l] : adj[v]) {
        if (u == prev) continue;
        d[v][l] = 1;
        dfs(k, u, v);
        for (auto[dist, r] : d[u]) {
            r++;
            if (d[v].count(l + dist))
                d[v][l + dist] = min(d[v][l + dist], r);
            else d[v][l + dist] = r;
        }
    }
    if (d[v].count(k)) res = min(res, d[v][k]);
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(K);
    return (res == 1e9 ? -1 : res);
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int)':
race.cpp:10:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for (auto[u, l] : adj[v]) {
      |              ^
race.cpp:14:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |         for (auto[dist, r] : d[u]) {
      |                  ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57