제출 #712193

#제출 시각아이디문제언어결과실행 시간메모리
712193noeditPastiri (COI20_pastiri)C++17
100 / 100
904 ms114288 KiB
#include <bits/stdc++.h> //#include <quadmath.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> //#define sz(x) (int)x.size() //#define sqr(x) x*x #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("fast-math") using namespace std; using namespace __gnu_pbds; //#define int long long //#define ld long double template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; const int INF = 2e9; vector<vector<int> > g; vector<int> dep; vector<bool> used; vector<vector<int> > up; vector<bool> deld; vector<int> dist; vector<int> sh; int l = 0; void calc(int v, int p, int d) { up[0][v] = p; for (int i = 1; i < l; i++) { up[i][v] = up[i - 1][up[i - 1][v]]; } dep[v] = d; for (auto& u : g[v]) { if (u != p) { calc(u, v, d + 1); } } } void del(int v, int p) { deld[v] = 1; for (auto& u : g[v]) { if (dist[u] < dist[v] && !deld[u] && u != p) { del(u, v); } } } void solve() { int n, k; cin >> n >> k; used.resize(n); dist.resize(n, INF); dep.resize(n); g.resize(n); deld.resize(n); sh.resize(k); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } while ((1 << l) <= n) { l++; } up.resize(l, vector<int>(n)); queue<int> q; for (int i = 0; i < k; i++) { int x; cin >> x; x--; sh[i] = x; dist[x] = 0; used[x] = 1; q.push(x); } while (!q.empty()) { int v = q.front(); q.pop(); for (auto& u : g[v]) { if (dist[u] > dist[v] + 1) { dist[u] = dist[v] + 1; q.push(u); } } } calc(0, 0, 0); vector<int> ans; sort(sh.begin(), sh.end(), [&](int i, int j) {return dep[i] > dep[j];}); for (int i = 0; i < k; i++) { if (deld[sh[i]]) continue; int a = sh[i]; for (int j = l - 1; j >= 0; j--) { if (dist[up[j][a]] == dist[a] + (1 << j)) { a = up[j][a]; } } ans.push_back(a); del(a, a); } cout << ans.size() << endl; for (auto& x : ans) cout << x + 1 << ' '; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t = 1; //cin >> t; while (t--) { solve(); } return 0; } /* 4 2 4 3 1 1 10 9 2 2 4 7 2 5 7; 4 1 8 10 5 3 5 6 5 9 1 10 */ /* 4 1 3 2 4 2 3 3 4 */ /* 1 1 1 100000000 1 1 1 1 1 */ /* ???????????????????????????????????????????????? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...