Submission #1093136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093136		vjudge1	Pastiri (COI20_pastiri)	C++17	49 / 100	1008 ms	71948 KiB

pastiri

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e5 + 5;

int n, k;
int p[kMaxN], dep[kMaxN], dis[kMaxN], id[kMaxN];
bool vis[kMaxN], del[kMaxN];
std::vector<int> G[kMaxN];

void bfs() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i)
    if (vis[i])
      q.emplace(i);
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (auto v : G[u]) {
      if (!vis[v]) {
        dis[v] = dis[u] + 1, vis[v] = 1;
        q.emplace(v);
      }
    }
  }
}

void dfs1(int u, int fa) {
  p[u] = fa, dep[u] = dep[fa] + 1;
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
  }
}

void dfs2(int u, int fa) {
  del[u] = 1;
  for (auto v : G[u]) {
    if (v == fa || dis[v] != dis[u] - 1) continue;
    dfs2(v, u);
  }
}

void dickdreamer() {
  std::cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  for (int i = 1; i <= k; ++i) {
    std::cin >> id[i];
    vis[id[i]] = 1;
  }
  bfs(), dfs1(1, 0);
  std::sort(id + 1, id + 1 + n, [&] (int i, int j) { return dep[i] > dep[j]; });
  std::vector<int> vec;
  for (int c = 1; c <= k; ++c) {
    int i = id[c];
    if (del[i]) continue;
    for (; p[i] && dis[p[i]] == dis[i] + 1; i = p[i]) {}
    dfs2(i, 0);
    vec.emplace_back(i);
  }
  std::cout << vec.size() << '\n';
  for (auto x : vec) std::cout << x << ' ';
}

int32_t main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51