제출 #378604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378604		schiftyfive4	경주 (Race) (IOI11_race)	C++14	0 / 100	4 ms	5100 KiB

race

#include "race.h"
#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 best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;
    for (int i = 0; i < n - 1; i++) {
        int u = H[i][0], v = H[i][1], w = L[i];
        std::cout << u << ' ' << v << ' ' << w << '\n';
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }
    Decompose(0);
    return ans == 1e9 ? -1 : ans;
}
// 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';
// }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int dfs(int, int)':
race.cpp:10:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'int Cen(int, int, int)':
race.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for (auto [v, w] : e[u]) {
      |               ^
race.cpp: In function 'void Decompose(int)':
race.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [v, w] : e[c]) {
      |               ^
race.cpp:43:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for (auto [len, dep] : path) {
      |                   ^
race.cpp:49:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for (auto [len, dep] : path) {
      |                   ^
race.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [v, w] : e[c]) {
      |               ^

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