結果

問題 No.3222 Let the World Forget Me
ユーザー Nauclhlt🪷
提出日時 2025-07-03 18:17:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,640 bytes
コンパイル時間 2,490 ms
コンパイル使用メモリ 213,404 KB
実行使用メモリ 7,952 KB
最終ジャッジ日時 2025-07-05 22:29:39
合計ジャッジ時間 8,443 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other RE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

    int N, M;
    cin >> N >> M;
    
    if (N == 1)
    {
        cout << 0 << endl;
        return 0;
    }

    vector<set<int>> adj(N, set<int>());
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;

        adj[a].insert(b);
        adj[b].insert(a);
    }

    vector<int> C(M);
    for (int i = 0; i < M; i++)
    {
        cin >> C[i];
    }

    vector<int> d(N, -1);
    queue<pair<int, int>> q;
    for (int i = 0; i < M; i++)
    {
        q.emplace(C[i] - 1, 0);
    }

    while (!q.empty())
    {
        int n = q.front().first;
        int dist = q.front().second;
        q.pop();

        if (d[n] != -1) continue;
        d[n] = dist;

        for (auto& x : adj[n])
        {
            q.emplace(x, dist + 1);
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << d[i] << endl;
    }

    int ans = 0;
    int t = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    for (int i = 0; i < N; i++)
    {
        if (adj[i].size() == 1)
        {
            pq.emplace(d[i], i);
        }
    }
    
    while (!pq.empty())
    {
        if (pq.empty()) break;
        int a = pq.top().first;
        int b = pq.top().second;
        pq.pop();

        if (t >= a) continue;

        ans++;
        t++;
        int p = *adj[a].begin();
        adj[p].erase(a);
        if (adj[p].size() == 1)
        {
            pq.emplace(d[p], p);
        }
    }

    cout << ans << endl;
}
0