Submission #382469

#TimeUsernameProblemLanguageResultExecution timeMemory
382469VEGAnnPastiri (COI20_pastiri)C++14
82 / 100
1018 ms107828 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() #define sz(x) ((int)x.size()) #define i2 array<int,2> #define PB push_back using namespace std; typedef long long ll; const int oo = 2e9; const int N = 500100; vector<i2> vc; vector<int> ans, g[N], nw_g[N]; bool mrk[N], mrk_ans[N]; int n, k, h[N], dst[N], sh[N], up[N]; void dfs(int v, int p){ dst[v] = oo; if (mrk[v]) dst[v] = 0; for (int u : g[v]){ if (u == p) continue; h[u] = h[v] + 1; dfs(u, v); dst[v] = min(dst[v], dst[u] + 1); } } void calc_dst(int v, int p, int mn_up){ int mn1 = oo, mn2 = oo; for (int u : g[v]){ if (u == p) continue; if (dst[u] + 1 < mn1){ mn2 = mn1; mn1 = dst[u] + 1; } else if (dst[u] + 1 < mn2) mn2 = dst[u] + 1; } if (mrk[v]) mn_up = 0; dst[v] = min(dst[v], mn_up); for (int u : g[v]){ if (u == p) continue; int nw = oo; if (dst[u] + 1 == mn1) nw = min(mn_up, mn2); else nw = min(mn_up, mn1); calc_dst(u, v, nw + 1); } } void calc_up(int v, int p){ if (v == 0) up[v] = 0; else { if (dst[v] == dst[p] - 1) up[v] = up[p]; else up[v] = v; } for (int u : g[v]){ if (u == p) continue; calc_up(u, v); } } void dfsik(int v){ mrk_ans[v] = 1; for (int u : nw_g[v]){ if (mrk_ans[u]) continue; dfsik(u); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n >> k; for (int i = 1; i < n; i++){ int x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); } for (int i = 0; i < k; i++){ int x; cin >> x; x--; sh[i] = x; mrk[x] = 1; } h[0] = 0; dfs(0, -1); calc_dst(0, -1, oo); for (int i = 0; i < n; i++) for (int u : g[i]) if (dst[i] - 1 == dst[u]) nw_g[i].PB(u); calc_up(0, -1); for (int i = 0; i < k; i++) vc.PB({h[sh[i]], sh[i]}); sort(all(vc)); reverse(all(vc)); for (i2 cr : vc){ int v = cr[1]; if (mrk_ans[v]) continue; int who = up[v]; ans.PB(who); dfsik(who); } cout << sz(ans) << '\n'; for (int cr : ans) cout << cr + 1 << " "; 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...