結果

問題 No.994 ばらばらコイン
ユーザー MisterMister
提出日時 2020-03-12 23:14:11
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,427 bytes
コンパイル時間 819 ms
コンパイル使用メモリ 94,528 KB
実行使用メモリ 16,756 KB
最終ジャッジ日時 2023-08-20 14:15:29
合計ジャッジ時間 2,162 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 39 ms
16,756 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 30 ms
7,744 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

using lint = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;

    Graph<> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        graph[u].emplace_back(u, v);
        graph[v].emplace_back(v, u);
    }

    std::vector<int> dist(n, 0);
    std::function<void(int, int, int)>
        dfs = [&](int v, int p, int d) {
            ++dist[d];
            for (auto e : graph[v]) {
                int u = e.dst;
                if (u == p) continue;
                dfs(u, v, d + 1);
            }
        };
    dfs(0, -1, 0);

    lint ans = 0;
    for (int d = 0; d < n; ++d) {
        lint r = std::min(dist[d], k);
        ans += r * d;
        k -= r;
    }

    std::cout << (k > 0 ? -1 : ans) << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}
0