#include <bits/stdc++.h>
using namespace std;
#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 bfs(int src) {
vis[src] = true;
queue<int> q;
q.emplace(src);
while (q.size()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (!vis[v] && mn[v] + 1 == mn[u]) {
vis[v] = true;
q.emplace(v);
}
}
}
}
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;
while (mn[par[v]] + h[par[v]] == h[u]) {
v = par[v];
}
res.emplace_back(v);
bfs(v);
}
}
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
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();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
160072 KB |
Output is correct |
2 |
Correct |
168 ms |
160084 KB |
Output is correct |
3 |
Correct |
182 ms |
160196 KB |
Output is correct |
4 |
Correct |
223 ms |
167348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
53852 KB |
Output is correct |
2 |
Correct |
20 ms |
54004 KB |
Output is correct |
3 |
Correct |
678 ms |
122804 KB |
Output is correct |
4 |
Correct |
689 ms |
125028 KB |
Output is correct |
5 |
Correct |
669 ms |
122732 KB |
Output is correct |
6 |
Correct |
690 ms |
125648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
49756 KB |
Output is correct |
2 |
Correct |
13 ms |
49792 KB |
Output is correct |
3 |
Correct |
31 ms |
49756 KB |
Output is correct |
4 |
Correct |
27 ms |
50012 KB |
Output is correct |
5 |
Correct |
34 ms |
49756 KB |
Output is correct |
6 |
Correct |
28 ms |
49756 KB |
Output is correct |
7 |
Correct |
11 ms |
49792 KB |
Output is correct |
8 |
Correct |
11 ms |
49752 KB |
Output is correct |
9 |
Correct |
11 ms |
49756 KB |
Output is correct |
10 |
Correct |
16 ms |
49796 KB |
Output is correct |
11 |
Correct |
14 ms |
49756 KB |
Output is correct |
12 |
Correct |
14 ms |
47712 KB |
Output is correct |
13 |
Correct |
29 ms |
49756 KB |
Output is correct |
14 |
Correct |
19 ms |
49840 KB |
Output is correct |
15 |
Correct |
23 ms |
49756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
539 ms |
125868 KB |
Output is correct |
2 |
Correct |
491 ms |
132492 KB |
Output is correct |
3 |
Correct |
585 ms |
135080 KB |
Output is correct |
4 |
Correct |
513 ms |
131624 KB |
Output is correct |
5 |
Correct |
431 ms |
130560 KB |
Output is correct |
6 |
Correct |
516 ms |
139832 KB |
Output is correct |
7 |
Correct |
529 ms |
137812 KB |
Output is correct |
8 |
Correct |
579 ms |
137300 KB |
Output is correct |
9 |
Correct |
554 ms |
132012 KB |
Output is correct |
10 |
Correct |
432 ms |
131744 KB |
Output is correct |
11 |
Correct |
313 ms |
133784 KB |
Output is correct |
12 |
Correct |
336 ms |
136532 KB |
Output is correct |
13 |
Correct |
348 ms |
138540 KB |
Output is correct |
14 |
Correct |
264 ms |
135252 KB |
Output is correct |
15 |
Correct |
42 ms |
80468 KB |
Output is correct |
16 |
Correct |
482 ms |
129876 KB |
Output is correct |
17 |
Correct |
335 ms |
131068 KB |
Output is correct |
18 |
Correct |
397 ms |
127316 KB |
Output is correct |
19 |
Correct |
490 ms |
137296 KB |
Output is correct |
20 |
Correct |
463 ms |
140812 KB |
Output is correct |
21 |
Correct |
377 ms |
131856 KB |
Output is correct |
22 |
Correct |
461 ms |
132436 KB |
Output is correct |