結果

問題 No.994 ばらばらコイン
ユーザー Mister
提出日時 2020-03-12 23:14:11
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,427 bytes
コンパイル時間 885 ms
コンパイル使用メモリ 130,292 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-11-30 16:54:23
合計ジャッジ時間 1,892 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます

ソースコード

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