結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-01 22:51:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 2,937 ms |
コンパイル使用メモリ | 291,576 KB |
実行使用メモリ | 15,964 KB |
最終ジャッジ日時 | 2025-08-01 22:52:04 |
合計ジャッジ時間 | 5,810 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int N,M; cin>>N>>M; int P[N+1]; int A[N],B[N]; int C[M+1]; for(int i=1;i<=N;i++) cin>>P[i]; vector<int>G[N+1]; for(int i=1;i<=N-1;i++){ cin>>A[i]>>B[i]; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } for(int i=1;i<=M;i++) cin>>C[i]; int dist[N+1]; bool already[N+1]; for(int i=1;i<=N;i++){ dist[i]=1e9; already[i]=0; } queue<int>Q; for(int i=1;i<=M;i++){ Q.push(C[i]); dist[C[i]]=0; } while(!Q.empty()){ int pos=Q.front(); Q.pop(); if(already[pos]) continue; already[pos]=1; for(int i=0;i<G[pos].size();i++){ int nex=G[pos][i]; if(already[nex]) continue; if(dist[nex]>dist[pos]+1){ dist[nex]=dist[pos]+1; Q.push(nex); } } } vector<pair<int,int>>polute[N+1]; for(int i=1;i<=N;i++){ polute[dist[i]].push_back({-P[i],i}); } set<pair<int,int>>leaf; for(int i=1;i<=N;i++){ if(G[i].size()==1) leaf.insert({-P[i],i}); } ll ans=0; int siz[N+1]; bool poluted[N+1]; for(int i=1;i<=N;i++){ siz[i]=G[i].size(); poluted[i]=0; } rep(j,polute[0].size()){ leaf.erase(polute[0][j]); poluted[polute[0][j].second]=1; } for(int i=1;i<=N;i++){ if(leaf.size()==0) break; ans-=(*leaf.begin()).first; int pos=(*leaf.begin()).second; leaf.erase(*leaf.begin()); rep(j,G[pos].size()){ int nex=G[pos][j]; siz[nex]--; if(siz[nex]==1 && poluted[nex]==0) leaf.insert({-P[nex],nex}); } rep(j,polute[i].size()){ leaf.erase(polute[i][j]); poluted[polute[i][j].second]=1; } } cout<<ans<<"\n"; }