結果

問題 No.994 ばらばらコイン
コンテスト
ユーザー Mister
提出日時 2020-03-12 23:14:11
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,427 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 980 ms
コンパイル使用メモリ 141,952 KB
実行使用メモリ 17,024 KB
最終ジャッジ日時 2026-05-24 07:49:13
合計ジャッジ時間 2,558 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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