Submission #792948

#	Time	Username	Problem	Language	Result	Execution time	Memory
792948		NoLove	Race (IOI11_race)	C++14	9 / 100	94 ms	20716 KiB

race

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

const int MAXN = 2e5 + 5;
map<chi, chi> d[MAXN]; // d[v][k]: the minimum number of highways with length exactly k and consting node v
vector<pair<chi, chi>> adj[MAXN];
chi res = 1e18;
void dfs(chi k, chi v = 0, chi 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;
        }
        d[u].clear();
    }
    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 == 1e18 ? -1 : res);
}

Compilation message (stderr)

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

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