Submission #378578

#	Time	Username	Problem	Language	Result	Execution time	Memory
378578		schiftyfive4	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
constexpr int N = 2e5;
int n, k, ans = 1e9;
int siz[N], del[N];
std::vector<std::pair<int, int>> path;
std::vector<std::vector<std::pair<int, int>>> e(N);
int dfs(int u, int p = -1) {
    siz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (del[v] || v == p)
            continue;
        siz[u] += dfs(v, u);
    }
    return siz[u];
}
void dfs2(int u, int dep, int len, int p) {
    path.emplace_back(len, dep);
    for (auto [v, w] : e[u]) {
        if (del[v] || v == p)
            continue;
        dfs2(v, dep + 1, len + w, u);
    }
}
int Cen(int u, int S, int p = -1) {
    for (auto [v, w] : e[u]) {
        if (del[v] || v == p)
            continue;
        if (2 * siz[v] > S)
            return Cen(v, S, u);
    }
    return u;
}
void Decompose(int u) {
    int c = Cen(u, dfs(u));
    std::map<int, int> dp, vis;
    vis[0] = 1;
    for (auto [v, w] : e[c]) {
        if (del[v])
            continue;
        path.clear();
        dfs2(v, 1, w, c);
        for (auto [len, dep] : path) {
            if (len > k)
                continue;
            if (vis[k - len])
                ans = std::min(ans, dep + dp[k - len]);
        }
        for (auto [len, dep] : path) {
            if (len > k)
                continue;
            if (vis[len] == 0 || dep < dp[len])
                dp[len] = dep;
            vis[len] = 1;
        }
    }
    del[c] = 1;
    for (auto [v, w] : e[c]) {
        if (!del[v])
            Decompose(v);
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }
    Decompose(0);
    std::cout << (ans == 1e9 ? -1 : ans) << '\n';
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:9:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    9 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'int Cen(int, int, int)':
race.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'void Decompose(int)':
race.cpp:37:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for (auto [v, w] : e[c]) {
      |               ^
race.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [len, dep] : path) {
      |                   ^
race.cpp:48:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for (auto [len, dep] : path) {
      |                   ^
race.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [v, w] : e[c]) {
      |               ^
/tmp/cc2HxQU7.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc1hh0po.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/cc1hh0po.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status