oj.uz

Submission #948327

# Submission time Handle Problem Language Result Execution time Memory
948327 2024-03-18T04:11:55 Z NeroZein Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 114672 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) {
  covered[v] = true; 
  for (int u : g[v]) {
    if (u == p) continue; 
    if (closest[u] == closest[v] - 1) {
      dfs2(u, v); 
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = pr[j][u];
    }
  }
  if (u == v) return v;
  for (int j = LOG - 1; j >= 0; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u]; v = pr[j][v];
    }
  }
  return pr[0][v];
}

int dist(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(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;
    //this part can be sped up with binary jumping.
    for (int j = LOG - 1; j >= 0; --j) {
      if (closest[pr[j][newShephered]] == up + (1 << j)) {
        newShephered = pr[j][newShephered];
        up += 1 << j;
      }
    }
    //while (pr[0][newShephered] != 0 && closest[pr[0][newShephered]] == up + 1) {
      //newShephered = pr[0][newShephered];
      //up++;
    //}
    dfs2(newShephered, newShephered);
    shepherds.push_back(newShephered);
  }
  sort(shepherds.begin(), shepherds.end());
  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 159 ms 110420 KB Output is correct
2 Correct 191 ms 110708 KB Output is correct
3 Correct 184 ms 110416 KB Output is correct
4 Correct 276 ms 114672 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 53848 KB Output is correct
2 Correct 10 ms 54020 KB Output is correct
3 Correct 421 ms 71824 KB Output is correct
4 Correct 379 ms 74068 KB Output is correct
5 Correct 455 ms 71476 KB Output is correct
6 Correct 932 ms 74852 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 53848 KB Output is correct
2 Correct 9 ms 53852 KB Output is correct
3 Correct 9 ms 53852 KB Output is correct
4 Correct 9 ms 53848 KB Output is correct
5 Correct 11 ms 53852 KB Output is correct
6 Correct 9 ms 53852 KB Output is correct
7 Correct 9 ms 53784 KB Output is correct
8 Correct 9 ms 53848 KB Output is correct
9 Correct 9 ms 53852 KB Output is correct
10 Correct 9 ms 53860 KB Output is correct
11 Correct 9 ms 53848 KB Output is correct
12 Correct 8 ms 53596 KB Output is correct
13 Correct 12 ms 53852 KB Output is correct
14 Correct 10 ms 53852 KB Output is correct
15 Correct 9 ms 53752 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 72528 KB Output is correct
2 Correct 439 ms 72260 KB Output is correct
3 Correct 694 ms 73812 KB Output is correct
4 Correct 432 ms 71572 KB Output is correct
5 Correct 594 ms 71008 KB Output is correct
6 Correct 666 ms 78928 KB Output is correct
7 Correct 862 ms 76864 KB Output is correct
8 Correct 765 ms 76820 KB Output is correct
9 Correct 617 ms 71452 KB Output is correct
10 Correct 437 ms 71332 KB Output is correct
11 Correct 391 ms 73636 KB Output is correct
12 Correct 418 ms 75912 KB Output is correct
13 Correct 395 ms 77176 KB Output is correct
14 Correct 361 ms 75076 KB Output is correct
15 Correct 51 ms 56748 KB Output is correct
16 Execution timed out 1098 ms 69940 KB Time limit exceeded
17 Halted 0 ms 0 KB -