oj.uz

Submission #948330

# Submission time Handle Problem Language Result Execution time Memory
948330 2024-03-18T04:17:31 Z NeroZein Pastiri (COI20_pastiri) C++17
100 / 100
 761 ms 114720 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int LOG = 20;
const int N = 5e5 + 5;

int dep[N];
int closest[N];
int pr[LOG][N];
bool covered[N];
vector<int> g[N];

void bfs(vector<int>& sheeps) {
  memset(closest, -1, sizeof closest);
  queue<int> que; 
  for (int sheep : sheeps) {
    que.push(sheep);
    closest[sheep] = 0; 
  }
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    for (int u : g[v]) {
      if (closest[u] == -1) {
        closest[u] = closest[v] + 1; 
        que.push(u); 
      }
    }
  }
}

void dfs(int v, int p) {
  for (int u : g[v]) {
    if (u == p) continue; 
    dep[u] = dep[v] + 1; 
    pr[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      pr[j][u] = pr[j - 1][pr[j - 1][u]];
    }
    dfs(u, v);
  }
}

void dfs2(int v, int p) {
  if (covered[v]) return;
  covered[v] = true; 
  for (int u : g[v]) {
    if (u == p) continue; 
    if (closest[u] == closest[v] - 1) {
      dfs2(u, v); 
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> sheeps(k);
  for (int i = 0; i < k; ++i) {
    cin >> sheeps[i];
  }
  dfs(1, 0);
  bfs(sheeps);
  sort(sheeps.begin(), sheeps.end(), [&](int u, int v) {
    return dep[u] < dep[v];
  });
  vector<int> shepherds;
  for (int i = k - 1; i >= 0; --i) {
    int sheep = sheeps[i];
    if (covered[sheep]) continue; 
    int up = 0;
    int newShephered = sheep;
    for (int j = LOG - 1; j >= 0; --j) {
      if (closest[pr[j][newShephered]] == up + (1 << j)) {
        newShephered = pr[j][newShephered];
        up += 1 << j;
      }
    }
    dfs2(newShephered, newShephered);
    shepherds.push_back(newShephered);
  }
  cout << shepherds.size() << '\n';
  for (int shepherd : shepherds) {
    cout << shepherd << ' ';
  }
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 110324 KB Output is correct
2 Correct 173 ms 110404 KB Output is correct
3 Correct 173 ms 110420 KB Output is correct
4 Correct 280 ms 114720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 54104 KB Output is correct
2 Correct 9 ms 53852 KB Output is correct
3 Correct 402 ms 71880 KB Output is correct
4 Correct 367 ms 74068 KB Output is correct
5 Correct 412 ms 71248 KB Output is correct
6 Correct 528 ms 74872 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53848 KB Output is correct
2 Correct 9 ms 53852 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 8 ms 53848 KB Output is correct
5 Correct 8 ms 53852 KB Output is correct
6 Correct 9 ms 53852 KB Output is correct
7 Correct 9 ms 53852 KB Output is correct
8 Correct 8 ms 53756 KB Output is correct
9 Correct 9 ms 53852 KB Output is correct
10 Correct 9 ms 53848 KB Output is correct
11 Correct 9 ms 53760 KB Output is correct
12 Correct 8 ms 53700 KB Output is correct
13 Correct 10 ms 53852 KB Output is correct
14 Correct 9 ms 53768 KB Output is correct
15 Correct 9 ms 53852 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 72604 KB Output is correct
2 Correct 466 ms 72532 KB Output is correct
3 Correct 678 ms 73996 KB Output is correct
4 Correct 400 ms 71248 KB Output is correct
5 Correct 539 ms 70856 KB Output is correct
6 Correct 590 ms 79076 KB Output is correct
7 Correct 761 ms 76940 KB Output is correct
8 Correct 754 ms 76768 KB Output is correct
9 Correct 491 ms 71496 KB Output is correct
10 Correct 456 ms 71252 KB Output is correct
11 Correct 365 ms 73300 KB Output is correct
12 Correct 368 ms 75864 KB Output is correct
13 Correct 369 ms 77264 KB Output is correct
14 Correct 335 ms 75068 KB Output is correct
15 Correct 59 ms 56660 KB Output is correct
16 Correct 561 ms 70228 KB Output is correct
17 Correct 591 ms 71112 KB Output is correct
18 Correct 412 ms 68156 KB Output is correct
19 Correct 620 ms 77656 KB Output is correct
20 Correct 704 ms 82732 KB Output is correct
21 Correct 436 ms 71472 KB Output is correct
22 Correct 458 ms 72312 KB Output is correct