Submission #1297256

#TimeUsernameProblemLanguageResultExecution timeMemory
1297256danirasillaPastiri (COI20_pastiri)C++20
100 / 100
293 ms86756 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]; pair<int, int> dfs(int nw, int pr, vector<int>& dis, vector<int>& res) { int up = -1; int down = -1; if (sh[nw]) down = 0; for (int w : g[nw]) { if (w == pr) continue; auto ww = dfs(w, nw, dis, res); if (ww.first != -1) { down = max(down, ww.first + 1); } else up = max(up, ww.second - 1); } if (up >= down || down == -1) return { -1, up }; if ((pr == -1 || dis[nw] >= dis[pr]) && down != -1) { res.push_back(nw); return { -1, dis[nw]}; } return { down, -1 }; } 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; for (int i = 0; i < n; i++) st[i] = g[i].size(); 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 (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 (dis[w] > dis[i]) sp[i] = false; vector<int> res; dfs(0, -1, dis, res); cout << res.size() << "\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...