Submission #481233

#TimeUsernameProblemLanguageResultExecution timeMemory
481233RainbowbunnyPastiri (COI20_pastiri)C++17
100 / 100
981 ms130884 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; const int INF = 1e9; int n, k, tim; int H[MAXN], d[MAXN], a[MAXN]; int up[MAXN][20], cnt[MAXN]; bool Vis[MAXN]; vector <int> Ans, V; vector <int> NAdj[MAXN]; vector <int> Adj[MAXN]; void DFS(int node, int p = 1) { up[node][0] = p; for(int i = 1; i <= 18; i++) { up[node][i] = up[up[node][i - 1]][i - 1]; } tim++; for(auto x : Adj[node]) { if(x == p) { continue; } H[x] = H[node] + 1; DFS(x, node); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); Ans.reserve(MAXN); V.reserve(MAXN); cin >> n >> k; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; Adj[u].push_back(v); Adj[v].push_back(u); } DFS(1); for(int i = 1; i <= n; i++) { d[i] = -1; } queue <int> BFS; for(int i = 1; i <= k; i++) { cin >> a[i]; d[a[i]] = 0; BFS.push(a[i]); V.push_back(a[i]); } while(BFS.empty() == false) { int node = BFS.front(); BFS.pop(); for(auto x : Adj[node]) { if(d[x] == -1) { d[x] = d[node] + 1; BFS.push(x); } if(d[x] == d[node] + 1) { NAdj[x].push_back(node); } } } sort(V.begin(), V.end(), [](int x, int y) { return H[x] > H[y]; }); for(auto x : V) { if(Vis[x]) { continue; } int cur = x; for(int i = 18; i >= 0; i--) { int nx = up[cur][i]; if(H[x] - H[nx] <= d[nx]) { cur = nx; } } if(Vis[cur]) { continue; } Ans.push_back(cur); queue <int> q; Vis[cur] = true; q.push(cur); while(q.empty() == false) { int node = q.front(); q.pop(); for(auto y : NAdj[node]) { if(!Vis[y]) { Vis[y] = true; q.push(y); } } } } cout << Ans.size() << '\n'; for(auto x : Ans) { cout << x << ' '; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...