結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-11 00:50:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,330 bytes |
コンパイル時間 | 2,890 ms |
コンパイル使用メモリ | 292,620 KB |
実行使用メモリ | 16,280 KB |
最終ジャッジ日時 | 2025-08-11 00:50:08 |
合計ジャッジ時間 | 5,347 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* 葉の頂点の純粋さの多重集合を持っておく。 これから純粋さが最大のものを答えに足し、多重集合から取り除く。 取り除くことで新たに葉になる頂点が出てくる可能性があることに注意。 時刻iに汚染されるような葉の頂点の集合v(i)を求めておき、(i<=10^5) 取り除くたびにiをインクリメントしてv(i)に対応する純粋さを多重集合から取り除く。 */ ll N, M; cin >> N >> M; vector<ll> P(N), deg(N); for (int i=0; i<N; i++) cin >> P[i]; vector<vector<ll>> E(N); for (int i=0; i<N-1; i++){ ll a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); deg[a]++; deg[b]++; } vector<ll> C(M); for (int i=0; i<M; i++){ cin >> C[i]; C[i]--; } vector<ll> dist(N, 1e9); queue<ll> que; for (int i=0; i<M; i++){ dist[C[i]] = 0; que.push(C[i]); } while(!que.empty()){ auto from = que.front(); que.pop(); for (auto to : E[from]){ if (dist[to] == 1e9){ dist[to] = dist[from]+1; que.push(to); } } } priority_queue<pair<ll, ll>> pq; vector<vector<ll>> v(N+1); vector<bool> ng(N); for (int i=0; i<M; i++) ng[C[i]] = 1; for (int i=0; i<N; i++){ if (deg[i] == 1) pq.push({P[i], i}); v[dist[i]].push_back(i); } ll ans=0, now=1, val; while(!pq.empty()){ while(!pq.empty() && ng[pq.top().second]) pq.pop(); if (!pq.empty()){ auto [val, from] = pq.top(); pq.pop(); ans += val; deg[from] = 0; for (auto to : E[from]){ deg[to]--; if (deg[to] == 1){ pq.push({P[to], to}); } } } if (now <= N) for (auto idx : v[now]) ng[idx] = 1; now++; } cout << ans << endl; return 0; }