#include <bits/stdc++.h>
using namespace std;
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "
#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << (x))
#define N 500005
#define LOG 20
int n, k;
int x[N];
int h[N];
int st[LOG][N << 1];
int tin[N];
int tout[N];
int lg[N << 1];
vector<int> g[N];
int min_by_time(int u, int v) {
return (tin[u] < tin[v] ? u : v);
}
int order;
void dfs(int u = 1) {
tin[u] = ++order;
st[0][order] = u;
for (int v : g[u]) {
if (!tin[v]) {
h[v] = h[u] + 1;
dfs(v);
st[0][++order] = u;
}
}
tout[u] = order;
}
void build_spt() {
for (int i = 2; i <= order; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int j = 1; j <= lg[order]; ++j) {
for (int i = 1; i + MASK(j) - 1 <= order; ++i) {
st[j][i] = min_by_time(st[j - 1][i], st[j - 1][i + MASK(j - 1)]);
}
}
}
int lca(int u, int v) {
int L = min(tin[u], tin[v]);
int R = max(tout[u], tout[v]);
int k = lg[R - L + 1];
return min_by_time(st[k][L], st[k][R - MASK(k) + 1]);
}
int dist(int u, int v) {
return h[u] + h[v] - 2 * h[lca(u, v)];
}
template<class A, class B>
bool mini(A &a, const B &b) {
return a > b ? (a = b), true : false;
}
namespace sub1 {
bool valid_input() {
bool test = true;
for (int i = 1; i <= n; ++i) {
for (int j : g[i]) {
test &= (abs(j - i) == 1);
}
}
return test;
}
int dp[2][N];
int child[2][N];
pair<int, int> par[2][N];
bool mid(int l, int r) {
return (l > 0 && (r - l) % 2 == 0);
}
void solve() {
sort(x + 1, x + k + 1);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = dp[1][0] = 0;
for (int i = 1; i <= k; ++i) {
// case 1: dat 1 con phu i va i - 1 (neu x[i] - x[i - 1] & 1)
if (mid(x[i - 1], x[i])) {
if (mini(dp[1][i], dp[0][i - 1] + 1)) {
child[1][i] = x[i - 1] + (x[i] - x[i - 1]) / 2;
par[1][i] = {0, i - 1};
}
}
// case 2: dat tai i
if (mini(dp[1][i], dp[1][i - 1] + 1)) {
child[1][i] = x[i];
par[1][i] = {1, i - 1};
}
// case 3: k dat tai i
dp[0][i] = dp[1][i - 1];
par[0][i] = {1, i - 1};
}
int t = 1;
vector<int> res;
do {
if (child[t][k]) {
res.emplace_back(child[t][k]);
}
pair<int, int> prv = par[t][k];
t = prv.first;
k = prv.second;
} while (k != 0);
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
exit(0);
}
}
namespace sub2 {
bool valid_input() {
return k <= 15;
}
int g[MASK(15)];
int child[MASK(15)];
pair<int, int> prv[MASK(15)];
vector<int> res;
void dfs(int u) {
if (g[u] <= 1) {
if (child[u]) {
res.emplace_back(child[u]);
}
return;
}
dfs(prv[u].first);
dfs(prv[u].second);
}
void solve() {
memset(g, 0x3f, sizeof(g));
g[0] = 0;
for (int i = 1; i <= n; ++i) {
int mn = n + 1, mask = 0;
for (int j = 1; j <= k; ++j) {
int dis = dist(i, x[j]);
if (mn > dis) {
mn = dis;
mask = MASK(j - 1);
} else if (mn == dis) {
mask |= MASK(j - 1);
}
}
if (mini(g[mask], 1)) {
child[mask] = i;
}
}
for (int mask = 0; mask < MASK(k); ++mask) {
for (int smask = mask; smask; smask = (smask - 1) & mask) {
if (mini(g[smask], g[mask])) {
child[smask] = child[mask];
}
}
}
for (int mask = 0; mask < MASK(k); ++mask) {
for (int smask = mask; smask; smask = (smask - 1) & mask) {
if (mini(g[mask], g[smask] + g[mask ^ smask])) {
prv[mask] = {smask, mask ^ smask};
}
}
}
dfs(MASK(k) - 1);
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
file("SHEEP");
cin >> n >> k;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs();
build_spt();
for (int i = 1; i <= k; ++i) {
cin >> x[i];
}
if (sub1::valid_input()) {
sub1::solve();
}
if (sub2::valid_input()) {
sub2::solve();
}
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:192:3: note: in expansion of macro 'file'
192 | file("SHEEP");
| ^~~~
pastiri.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:192:3: note: in expansion of macro 'file'
192 | file("SHEEP");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
159276 KB |
Output is correct |
| 2 |
Correct |
146 ms |
159056 KB |
Output is correct |
| 3 |
Correct |
145 ms |
159056 KB |
Output is correct |
| 4 |
Correct |
200 ms |
166012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
52052 KB |
Output is correct |
| 2 |
Correct |
18 ms |
52060 KB |
Output is correct |
| 3 |
Correct |
556 ms |
120052 KB |
Output is correct |
| 4 |
Correct |
524 ms |
128852 KB |
Output is correct |
| 5 |
Correct |
517 ms |
126580 KB |
Output is correct |
| 6 |
Correct |
591 ms |
129436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
45660 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
313 ms |
118476 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
