oj.uz

Submission #1082151

# Submission time Handle Problem Language Result Execution time Memory
1082151 2024-08-30T19:19:52 Z juicy Pastiri (COI20_pastiri) C++17
100 / 100
 507 ms 78364 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 71712 KB Output is correct
2 Correct 148 ms 71924 KB Output is correct
3 Correct 154 ms 71928 KB Output is correct
4 Correct 240 ms 78364 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 9 ms 14424 KB Output is correct
3 Correct 303 ms 40956 KB Output is correct
4 Correct 237 ms 43252 KB Output is correct
5 Correct 333 ms 40688 KB Output is correct
6 Correct 507 ms 43600 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14268 KB Output is correct
2 Correct 8 ms 14172 KB Output is correct
3 Correct 6 ms 14172 KB Output is correct
4 Correct 8 ms 14172 KB Output is correct
5 Correct 6 ms 14168 KB Output is correct
6 Correct 6 ms 14168 KB Output is correct
7 Correct 6 ms 14172 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 7 ms 14172 KB Output is correct
11 Correct 7 ms 14172 KB Output is correct
12 Correct 6 ms 14172 KB Output is correct
13 Correct 7 ms 14172 KB Output is correct
14 Correct 6 ms 14336 KB Output is correct
15 Correct 7 ms 14172 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 41808 KB Output is correct
2 Correct 318 ms 41808 KB Output is correct
3 Correct 393 ms 44812 KB Output is correct
4 Correct 333 ms 40800 KB Output is correct
5 Correct 228 ms 39884 KB Output is correct
6 Correct 324 ms 48824 KB Output is correct
7 Correct 404 ms 47440 KB Output is correct
8 Correct 329 ms 46916 KB Output is correct
9 Correct 387 ms 40788 KB Output is correct
10 Correct 286 ms 40784 KB Output is correct
11 Correct 203 ms 42836 KB Output is correct
12 Correct 201 ms 46408 KB Output is correct
13 Correct 256 ms 48692 KB Output is correct
14 Correct 183 ms 44076 KB Output is correct
15 Correct 32 ms 18524 KB Output is correct
16 Correct 404 ms 38996 KB Output is correct
17 Correct 206 ms 40416 KB Output is correct
18 Correct 300 ms 35888 KB Output is correct
19 Correct 315 ms 46928 KB Output is correct
20 Correct 366 ms 50228 KB Output is correct
21 Correct 293 ms 41000 KB Output is correct
22 Correct 242 ms 41556 KB Output is correct