#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 par[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;
par[v] = u;
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 << " ";
}
exit(0);
}
}
namespace sub3 {
bool valid_input() {
return n <= 2000;
}
int mn[2005];
bool vis[2005];
void solve() {
for (int i = 1; i <= n; ++i) {
mn[i] = n + 1;
for (int j = 1; j <= k; ++j) {
mn[i] = min(mn[i], dist(i, x[j]));
}
}
sort(x + 1, x + k + 1, [&](int x, int y) {
return h[x] > h[y];
});
vector<int> res;
for (int i = 1; i <= k; ++i) {
int u = x[i];
if (!vis[u]) {
int v = -1;
for (int j = 1; j <= n; ++j) {
if (mn[j] == dist(u, j)) {
if (v == -1 || h[v] > h[j]) {
v = j;
}
}
}
res.emplace_back(v);
for (int j = 1; j <= k; ++j) {
if (mn[v] == dist(x[j], v)) {
vis[x[j]] = true;
}
}
}
}
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
exit(0);
}
}
namespace sub4 {
int mn[N];
bool vis[N];
void dfs(int u, int d) {
vis[u] = true;
if (d > 0) {
for (int v : g[u]) {
dfs(v, d - 1);
}
}
}
void solve() {
memset(mn, -1, sizeof(mn));
queue<int> q;
for (int i = 1; i <= k; ++i) {
mn[x[i]] = 0;
q.emplace(x[i]);
}
while (q.size()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (mn[v] == -1) {
mn[v] = mn[u] + 1;
q.emplace(v);
}
}
}
sort(x + 1, x + k + 1, [&](int i, int j) {
return h[i] > h[j];
});
vector<int> res;
for (int i = 1; i <= k; ++i) {
int u = x[i];
if (!vis[u]) {
int v = u, spec = v;
do {
if (mn[v] + h[v] == h[u]) {
spec = v;
}
v = par[v];
} while (v);
res.emplace_back(spec);
dfs(spec, mn[spec]);
}
}
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();
}
if (sub3::valid_input()) {
sub3::solve();
}
sub4::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:296:3: note: in expansion of macro 'file'
296 | 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:296:3: note: in expansion of macro 'file'
296 | file("SHEEP");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
163664 KB |
Output is correct |
| 2 |
Correct |
150 ms |
163668 KB |
Output is correct |
| 3 |
Correct |
152 ms |
163920 KB |
Output is correct |
| 4 |
Correct |
204 ms |
171724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
53848 KB |
Output is correct |
| 2 |
Correct |
18 ms |
54236 KB |
Output is correct |
| 3 |
Correct |
497 ms |
126292 KB |
Output is correct |
| 4 |
Correct |
558 ms |
128596 KB |
Output is correct |
| 5 |
Correct |
552 ms |
126292 KB |
Output is correct |
| 6 |
Correct |
554 ms |
129232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
49724 KB |
Output is correct |
| 2 |
Correct |
13 ms |
49736 KB |
Output is correct |
| 3 |
Correct |
27 ms |
49756 KB |
Output is correct |
| 4 |
Correct |
23 ms |
49752 KB |
Output is correct |
| 5 |
Correct |
31 ms |
49756 KB |
Output is correct |
| 6 |
Correct |
28 ms |
49752 KB |
Output is correct |
| 7 |
Correct |
9 ms |
49756 KB |
Output is correct |
| 8 |
Correct |
9 ms |
49808 KB |
Output is correct |
| 9 |
Correct |
11 ms |
49752 KB |
Output is correct |
| 10 |
Correct |
12 ms |
49756 KB |
Output is correct |
| 11 |
Correct |
14 ms |
49756 KB |
Output is correct |
| 12 |
Correct |
13 ms |
47928 KB |
Output is correct |
| 13 |
Correct |
27 ms |
49808 KB |
Output is correct |
| 14 |
Correct |
19 ms |
49756 KB |
Output is correct |
| 15 |
Correct |
23 ms |
49756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
129360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
