Submission #1297217

#TimeUsernameProblemLanguageResultExecution timeMemory
1297217danirasillaPastiri (COI20_pastiri)C++20
0 / 100
282 ms40072 KiB
#include <iostream> #include <string> #include <algorithm> #include <iomanip> #include <vector> #include <map> #include <iterator> #include <set> #include <random> #include <unordered_map> #include <queue> #include <cassert> #include <stack> #include <numeric> #include <deque> using namespace std; typedef long long ll; typedef long double ld; const ll md1 = 1'000'000'000; const ll md2 = 998244353; const ll mdd = 666013; int n, k; const int N = 500'001; vector<int> g[N]; bool sh[N]; void dfs(int nw, vector<bool>& alive, vector<int>& dis, queue<int>& q) { if (alive[nw]) q.push(nw); alive[nw] = false; sh[nw] = false; for (int w : g[nw]) { if (alive[w]) { if (dis[w] < dis[nw]) dfs(w, alive, dis, q); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { cin >> n >> k; vector<pair<int, int>> e(n - 1); for (int i = 1; i < n; i++) { int v, u; cin >> v >> u; v--, u--; e[i - 1] = { v, u }; g[v].push_back(u); g[u].push_back(v); } for (int i = 0; i < k; i++) { int v; cin >> v; sh[v - 1] = true; } vector<int> st(n); queue<int> q; vector<bool> alive(n, true); for (int i = 0; i < n; i++) { st[i] = g[i].size(); if (st[i] == 1 && !sh[i]) { q.push(i); alive[i] = false; } } while (!q.empty()) { int nw = q.front(); q.pop(); for (int w : g[nw]) { st[w]--; if (alive[w] && !sh[w] && st[w] == 1) { q.push(w); alive[w] = false; } } } vector<int> dis(n, -1); for (int i = 0; i < n; i++) { if (sh[i]) { q.push(i); dis[i] = 0; } } while (!q.empty()) { int nw = q.front(); q.pop(); for (int w : g[nw]) { if (alive[w] && dis[w] == -1) { dis[w] = dis[nw] + 1; q.push(w); } } } vector<bool> sp(n, true); for (int i = 0; i < n; i++) for (int w : g[i]) if (alive[w] && dis[w] > dis[i]) sp[i] = false; int ans = 0; vector<int> res; for (int i = 0; i < n; i++) if (st[i] <= 1 && alive[i]) { q.push(i); alive[i] = false; } while (!q.empty()) { int nw = q.front(); q.pop(); if (sp[nw] && sh[nw]) { ans++; res.push_back(nw); sp[nw] = false; dfs(nw, alive, dis, q); } for (int w : g[nw]) { st[w]--; if (sh[nw]) sh[w] = true; if (sp[nw]) sp[w] = true; if (alive[w] && st[w] <= 1) { q.push(w); alive[w] = false; } } } cout << ans << "\n"; sort(res.begin(), res.end()); for (int w : res) cout << w + 1 << " "; cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...