Submission #1082151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082151		juicy	Pastiri (COI20_pastiri)	C++17	100 / 100	507 ms	78364 KiB

pastiri

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5;

int n, k;
int d[N], s[N], pr[N], dep[N];
bool del[N];
vector<int> g[N];

void dfs(int u) {
  for (int v : g[u]) {
    if (v != pr[u]) {
      dep[v] = dep[u] + 1;
      pr[v] = u;
      dfs(v);
    }
  }
}

void DFS(int u) {
  del[u] = 1;
  for (int v : g[u]) {
    if (!del[v] && d[v] + 1 == d[u]) {
      DFS(v);
    }
  }
}

void bfs() {
  memset(d, -1, sizeof(d));
  queue<int> q;
  for (int i = 1; i <= k; ++i) {
    d[s[i]] = 0;
    q.push(s[i]);
  } 
  while (q.size()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= k; ++i) {
    cin >> s[i];
  } 
  bfs();
  dfs(1);
  sort(s + 1, s + k + 1, [&](int i, int j) {
    return dep[i] > dep[j];
  });
  vector<int> res;
  for (int i = 1; i <= k; ++i) {
    if (del[s[i]]) {
      continue;
    }
    int u = s[i], p = u;
    while (d[pr[p]] == dep[u] - dep[pr[p]]) {
      p = pr[p];
    }
    DFS(p);
    res.push_back(p);
  }
  cout << res.size() << "\n";
  for (int x : res) {
    cout << x << " ";
  }
  return 0;
}

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