結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-01 22:04:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,224 bytes |
コンパイル時間 | 3,673 ms |
コンパイル使用メモリ | 296,352 KB |
実行使用メモリ | 19,220 KB |
最終ジャッジ日時 | 2025-08-01 22:04:08 |
合計ジャッジ時間 | 7,540 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 WA * 4 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template <class T> using MaxHeap = std::priority_queue<T>; template <class T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>; #define rep2(i, n) for (ll i = 0; i < (n); i++) #define rep3(i, l, r) for (ll i = (l); i < (r); i++) #define rrep2(i, n) for (ll i = n; i-- > 0;) #define rrep3(i, r, l) for (ll i = (r); i-- > (l);) #define overload(a, b, c, d, ...) d #define rep(...) overload(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rrep(...) overload(__VA_ARGS__, rrep3, rrep2)(__VA_ARGS__) #define all(x) begin(x), end(x) bool chmin(auto& lhs, auto rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; } bool chmax(auto& lhs, auto rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; } struct IOIO { IOIO() { std::cin.tie(0)->sync_with_stdio(0); } } ioio; void solve() { int n, m; cin >> n >> m; vector<ll> p(n); rep(i, n) cin >> p[i]; vector graph(n, set<int>()); rep(i, n - 1) { int u, v; cin >> u >> v; u--; v--; graph[u].insert(v); graph[v].insert(u); } vector<int> c(m); rep(i, m) cin >> c[i], c[i]--; vector<int> ids(n); iota(all(ids), 0); sort(all(ids), [&](auto l, auto r) { return p[l] > p[r]; }); vector<int> cur = c; vector<bool> already(n); for (auto v: c) already[v] = true; ll ans = 0; int ids_i = 0; while (true) { for (; ids_i < n; ids_i++) { int i = ids[ids_i]; if (already[i]) continue; if (ssize(graph[i]) != 1) continue; int v = *graph[i].begin(); ans += p[i]; ids_i++; graph[i].erase(v); graph[v].erase(i); break; } if (ids_i == n) break; vector<int> nxt; for (auto u: cur) { for (auto v: graph[u]) { if (already[v]) continue; already[v] = true; nxt.push_back(v); } } cur = std::move(nxt); } cout << ans << '\n'; } int main() { int t = 1; // cin >> t; while (t--) solve(); }