Submission #714491

#TimeUsernameProblemLanguageResultExecution timeMemory
714491nifeshePastiri (COI20_pastiri)C++17
100 / 100
822 ms100868 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> //#pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #define f first #define s second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int) (x).size()) #define pb push_back #define mp make_pair //#define int long long using namespace std; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; } template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; } typedef long long ll; typedef long double ld; const ll mod = 1e9 + 7; const ll base = 1e6 + 9; const ll inf = 1e9; const int MAX = 5e5 + 15; const int LG = 19; random_device rd; mt19937 gen(rd()); uniform_int_distribution<ll> dis(1, inf); int n; int timer = 0; int tin[MAX], tout[MAX], d[MAX]; int up[MAX][LG]; vector<int> g[MAX]; void dfs(int v, int p = 0) { tin[v] = timer++; up[v][0] = p; for(auto to : g[v]) { if(to == p) continue; d[to] = d[v] + 1; dfs(to, v); } tout[v] = timer; } bool anc(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); } int LCA(int u, int v) { if(anc(u, v)) return u; if(anc(v, u)) return v; for(int l = LG - 1; ~l; l--) { if(!anc(up[u][l], v)) u = up[u][l]; } return up[u][0]; } int dist(int u, int v) { return d[u] + d[v] - 2 * d[LCA(u, v)]; } void solve() { int k; cin >> n >> k; for(int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } vector<int> a(k); for(auto &i : a) { cin >> i; } dfs(1); for(int l = 1; l < LG; l++) { for(int v = 1; v <= n; v++) { up[v][l] = up[up[v][l - 1]][l - 1]; } } vector<int> dist(n + 1, inf); queue<int> q; for(auto v : a) { dist[v] = 0; q.push(v); } while(sz(q)) { int v = q.front(); q.pop(); for(auto to : g[v]) { if(dist[to] > dist[v] + 1) { dist[to] = dist[v] + 1; q.push(to); } } } vector<int> ans; vector<pair<int, int>> order; vector<int> c(n + 1); for(auto v : a) c[v] = 1; for(auto v : a) order.pb({d[v], v}); sort(rall(order)); vector<int> used(n + 1); function<void(int, int)> update = [&](int v, int dst) { used[v] = 1; if(dst == 0) return; for(auto to : g[v]) { if(used[to] || (dist[to] != dist[v] - 1)) continue; update(to, dst - 1); } }; for(auto [useless, v] : order) { if(used[v]) continue; int u = v; for(int l = LG - 1; ~l; l--) { if(dist[up[u][l]] == d[v] - d[up[u][l]]) u = up[u][l]; } update(u, dist[u]); ans.pb(u); } sort(all(ans)); cout << sz(ans) << '\n'; for(auto v : ans) cout << v << " "; } signed main() { tout[0] = inf; d[0] = -inf; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ttt = 1; // cin >> ttt; while(ttt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...