제출 #381599

#제출 시각아이디문제언어결과실행 시간메모리
381599NONAMEPastiri (COI20_pastiri)C++17
8 / 100
1101 ms73988 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);} template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);} const int man = (int)(5e5 + 500); int n, m, timer; int a[man], tin[man], tout[man], h[man], dp[man], pr[man]; int up[man][20]; bool gd; vector <int> vc, g[man], all; inline void cls() { vc.clear(); gd = true; timer = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < 20; ++j) { up[i][j] = -1; } h[i] = 0; g[i].clear(); tin[i] = tout[i] = 0; } } void dfs(int v, int pr) { tin[v] = timer++; up[v][0] = pr; for (int i = 1; i < 20; ++i) { if (up[v][i - 1] != -1) { up[v][i] = up[up[v][i - 1]][i - 1]; } } for (auto& u : g[v]) { if (u == pr) { continue; } h[u] = h[v] + 1; dfs(u, v); } tout[v] = timer++; } bool upper(int v, int u) { return ((tin[v] <= tin[u]) && (tout[v] >= tout[u])); } int lca(int v, int u) { if (upper(v, u)) { return v; } if (upper(u, v)) { return u; } for (int i = 19; i >= 0; --i) { if ((up[v][i] != -1) && !upper(up[v][i], u)) { v = up[v][i]; } } return up[v][0]; } void solve() { cls(); cin >> n >> m; for (int i = 0; i < (n - 1); ++i) { int x, y; cin >> x >> y; --x, --y; gd &= (abs(x - y) == 1); g[x].push_back(y); g[y].push_back(x); } for (int i = 0; i < m; ++i) { cin >> a[i]; --a[i]; } if (gd) { sort(a, a + m); for (int i = 0; i < m; ++i) { if (i == (m - 1)) { vc.push_back(a[i]); } else { int md = (a[i] + a[i + 1]) >> 1; vc.push_back(md); if (abs(a[i] - md) == abs(a[i + 1] - md)) { ++i; } } } } else { dfs(0, -1); for (int i = 0; i < n; ++i) { int mn = 1e9; for (int j = 0; j < m; ++j) { mn = min(mn, h[i] + h[a[j]] - 2 * h[lca(i, a[j])]); } int msk = 0; for (int j = 0; j < m; ++j) { if ((h[i] + h[a[j]] - (2 * h[lca(i, a[j])])) == mn) { msk |= (1 << j); } } all.push_back(msk); } sort(all.begin(), all.end()); all.resize(unique(all.begin(), all.end()) - all.begin()); for (int msk = 0; msk < (1 << m); ++msk) { dp[msk] = 1e9; } dp[0] = 0; for (int msk = 0; msk < (1 << m); ++msk) { for (int i = 0; i < (int)(all.size()); ++i) { int nmsk = msk | all[i]; if (chmin(dp[nmsk], dp[msk] + 1)) { pr[nmsk] = msk; } } } int msk = (1 << m) - 1; while (msk > 0) { int need = msk ^ pr[msk]; int p = -1; for (int i = 0; i < n; ++i) { int mn = 1e9; for (int j = 0; j < m; ++j) { mn = min(mn, h[i] + h[a[j]] - 2 * h[lca(i, a[j])]); } int curMsk = 0; for (int j = 0; j < m; ++j) { if ((h[i] + h[a[j]] - (2 * h[lca(i, a[j])])) == mn) { curMsk |= (1 << j); } } if ((curMsk & need) == need) { p = i; break; } } assert(p != -1); vc.push_back(p); msk = pr[msk]; } } sort(vc.begin(), vc.end()); cout << (int)(vc.size()) << "\n"; for (auto& i : vc) { cout << (i + 1) << " "; } cout << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; #ifdef _LOCAL system("color a"); freopen("in.txt", "r", stdin); cin >> t; #endif for (int i = 1; i <= t; ++i) { cerr << "Case #" << i << ": \n"; solve(); cerr << "\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...