結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-01 22:57:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,146 bytes |
コンパイル時間 | 1,555 ms |
コンパイル使用メモリ | 133,220 KB |
実行使用メモリ | 10,356 KB |
最終ジャッジ日時 | 2025-08-01 22:58:11 |
合計ジャッジ時間 | 3,647 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 WA * 2 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <numeric> #include <tuple> #include <ranges> namespace ranges = std::ranges; namespace views = std::views; // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; #include <queue> using namespace std; int N, M, P[100010], C[100010]; vector<int> g[100010]; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> N >> M; for (int i = 0 ; i < N ; i++) cin >> P[i]; for (int i = 0 ; i < N - 1 ; i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } vector<int> dist(N, -1); { vector<int> que; for (int i = 0 ; i < M ; i++) { int C; cin >> C; C--; dist[C] = 0; que.push_back(C); } for (int t = 0 ; t < ssize(que) ; t++) { const int v = que[t]; for (int x : g[v]) if (dist[x] == -1) { dist[x] = dist[v] + 1; que.push_back(x); } } } vector<bool> vis(N); priority_queue<pair<int, int>> que; for (int i = 0 ; i < N ; i++) if (ssize(g[i]) == 1) { vis[i] = true; que.push({P[i], i}); } long long ans = 0LL; for (int t = 0 ; que.size() ; t++) { auto [p, v] = que.top(); que.pop(); if (t < dist[v]) { ans += p; for (int x : g[v]) if (!vis[x]) { vis[x] = true; que.push({P[x], x}); } } else t--; } cout << ans << '\n'; }