結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-11 00:36:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,868 bytes |
コンパイル時間 | 4,087 ms |
コンパイル使用メモリ | 288,548 KB |
実行使用メモリ | 15,024 KB |
最終ジャッジ日時 | 2025-08-11 00:37:03 |
合計ジャッジ時間 | 7,064 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 WA * 6 |
ソースコード
#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); 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); } 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); } } } multiset<ll> st; vector<vector<ll>> v(N+1); for (int i=0; i<N; i++){ if (E[i].size() == 1){ if (dist[i] > 0) st.insert(P[i]); v[dist[i]].push_back(i); } } ll ans=0, now=1, val; while(!st.empty() && now <= N){ val = *st.rbegin(); ans += val; st.erase(st.find(val)); for (auto x : v[now]) if (st.count(P[x])) st.erase(st.find(P[x])); now++; } cout << ans << endl; return 0; }