結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
|
提出日時 | 2025-08-01 22:56:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 2,013 bytes |
コンパイル時間 | 2,296 ms |
コンパイル使用メモリ | 214,308 KB |
実行使用メモリ | 11,500 KB |
最終ジャッジ日時 | 2025-08-01 22:56:45 |
合計ジャッジ時間 | 4,757 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.h> #else #define dbg(...) 0 #define dbgn(...) 0 #endif void solve() { int n, m; cin >> n >> m; vector<ll> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } vector<vector<int>> adj(n); vector<int> degree(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; adj[u].push_back(v); adj[v].push_back(u); degree[u]++; degree[v]++; } vector<int> ct(n, 1e9); queue<int> q; for (int i = 0; i < m; i++) { int x; cin >> x; x--; ct[x] = 0; q.push(x); } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (ct[v] == 1e9) { ct[v] = ct[u] + 1; q.push(v); } } } priority_queue<tuple<ll, int, int>> pq; for (int i = 0; i < n; i++) { if (degree[i] == 1) { pq.push({p[i], ct[i], i}); } } vector<bool> rem(n, false); ll ans = 0; for (int t = 1; t <= n; t++) { bool cr = false; while (!pq.empty()) { auto [pur, c_time, idx] = pq.top(); if (rem[idx]) { pq.pop(); continue; } if (c_time >= t) { pq.pop(); ans += pur; rem[idx] = true; cr = true; for (int x : adj[idx]) { if (!rem[x]) { degree[x]--; if (degree[x] == 1) { pq.push({p[x], ct[x], x}); } } } break; } else pq.pop(); } if (!cr) break; } cout << ans << '\n'; } int32_t main() { cin.tie(0)->sync_with_stdio(0); solve(); return 0; }