oj.uz

Submission #1093136

# Submission time Handle Problem Language Result Execution time Memory
1093136 2024-09-26T02:35:53 Z vjudge1 Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 71948 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 66132 KB Output is correct
2 Correct 145 ms 66596 KB Output is correct
3 Correct 149 ms 66644 KB Output is correct
4 Correct 186 ms 71948 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12380 KB Output is correct
2 Correct 6 ms 12380 KB Output is correct
3 Correct 221 ms 43484 KB Output is correct
4 Correct 239 ms 45652 KB Output is correct
5 Correct 270 ms 43084 KB Output is correct
6 Correct 578 ms 45144 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 5 ms 12120 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 6 ms 12380 KB Output is correct
7 Correct 6 ms 12124 KB Output is correct
8 Correct 6 ms 12124 KB Output is correct
9 Correct 7 ms 12124 KB Output is correct
10 Correct 6 ms 12124 KB Output is correct
11 Correct 6 ms 12124 KB Output is correct
12 Correct 6 ms 12124 KB Output is correct
13 Correct 7 ms 12124 KB Output is correct
14 Correct 6 ms 12220 KB Output is correct
15 Correct 6 ms 12120 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 44112 KB Output is correct
2 Correct 275 ms 43856 KB Output is correct
3 Correct 287 ms 46284 KB Output is correct
4 Correct 269 ms 43088 KB Output is correct
5 Correct 185 ms 40652 KB Output is correct
6 Correct 291 ms 49504 KB Output is correct
7 Correct 293 ms 48152 KB Output is correct
8 Correct 317 ms 48288 KB Output is correct
9 Correct 394 ms 43560 KB Output is correct
10 Correct 299 ms 43088 KB Output is correct
11 Correct 199 ms 45316 KB Output is correct
12 Correct 200 ms 47732 KB Output is correct
13 Correct 220 ms 49260 KB Output is correct
14 Correct 182 ms 46432 KB Output is correct
15 Correct 38 ms 17244 KB Output is correct
16 Execution timed out 1008 ms 40784 KB Time limit exceeded
17 Halted 0 ms 0 KB -