oj.uz

Submission #773837

# Submission time Handle Problem Language Result Execution time Memory
773837 2023-07-05T09:01:04 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 552 ms 86148 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;

int N, K;
int sheep[MAXN];
vector <int> adj[MAXN];
int dep[MAXN], dist[MAXN];
int highest[MAXN];
bool bio[MAXN];

void load() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i < N; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 0; i < K; i++)
    scanf("%d", sheep + i);
}

void dfs_init(int x, int p, int mx, int opt) {
  int sum = dep[x] + dist[x];
  if (sum > mx) {
    mx = sum;
    opt = x;
  }
  highest[x] = opt;
  for (auto it : adj[x])
    if (it != p) {
      dep[it] = dep[x] + 1;
      dfs_init(it, x, mx, opt);
    }
}

void bfs() {
  memset(dist, -1, sizeof dist);
  queue <int> Q;
  for (int i = 0; i < K; i++) {
    dist[sheep[i]] = 0;
    Q.push(sheep[i]);
  }
  while (!Q.empty()) {
    int curr = Q.front();
    Q.pop();
    for (auto it : adj[curr])
      if (dist[it] == -1) {
        dist[it] = dist[curr] + 1;
        Q.push(it);
      }
  }
}

void dfs_cover(int x) {
  bio[x] = true;
  for (auto it : adj[x])
    if (!bio[it] && dist[x] == dist[it] + 1)
      dfs_cover(it);
}

void solve() {
  bfs();
  dfs_init(1, 0, -1, 0);
  sort(sheep, sheep + K, [](int x, int y) { return dep[x] > dep[y]; });
  vector <int> ans;
  for (int i = 0; i < K; i++)
    if (!bio[sheep[i]]) {
      ans.push_back(highest[sheep[i]]);
      dfs_cover(highest[sheep[i]]);
    }
  printf("%d\n", ans.size());
  for (auto it : ans)
    printf("%d ", it);
  puts("");
}

int main() {
  load();
  solve();
  return 0;
}

Compilation message

pastiri.cpp: In function 'void solve()':
pastiri.cpp:74:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   74 |   printf("%d\n", ans.size());
      |           ~^     ~~~~~~~~~~
      |            |             |
      |            int           std::vector<int>::size_type {aka long unsigned int}
      |           %ld
pastiri.cpp: In function 'void load()':
pastiri.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d", &N, &K);
      |   ~~~~~^~~~~~~~~~~~~~~~
pastiri.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
pastiri.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d", sheep + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 72908 KB Output is correct
2 Correct 175 ms 73288 KB Output is correct
3 Correct 181 ms 79824 KB Output is correct
4 Correct 262 ms 86148 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14244 KB Output is correct
2 Correct 8 ms 14232 KB Output is correct
3 Correct 369 ms 34372 KB Output is correct
4 Correct 397 ms 36812 KB Output is correct
5 Correct 439 ms 40684 KB Output is correct
6 Correct 552 ms 44236 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14044 KB Output is correct
2 Correct 8 ms 14024 KB Output is correct
3 Correct 8 ms 14132 KB Output is correct
4 Correct 7 ms 14044 KB Output is correct
5 Correct 9 ms 14100 KB Output is correct
6 Correct 8 ms 14120 KB Output is correct
7 Correct 9 ms 14120 KB Output is correct
8 Correct 9 ms 14120 KB Output is correct
9 Correct 7 ms 14036 KB Output is correct
10 Correct 6 ms 14036 KB Output is correct
11 Correct 6 ms 13996 KB Output is correct
12 Correct 6 ms 13988 KB Output is correct
13 Correct 7 ms 14036 KB Output is correct
14 Correct 7 ms 14116 KB Output is correct
15 Correct 7 ms 14036 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 35244 KB Output is correct
2 Correct 381 ms 41716 KB Output is correct
3 Correct 486 ms 44548 KB Output is correct
4 Correct 467 ms 40732 KB Output is correct
5 Correct 295 ms 39800 KB Output is correct
6 Correct 408 ms 49556 KB Output is correct
7 Correct 501 ms 47908 KB Output is correct
8 Correct 429 ms 47360 KB Output is correct
9 Correct 520 ms 40900 KB Output is correct
10 Correct 417 ms 40684 KB Output is correct
11 Correct 295 ms 42768 KB Output is correct
12 Correct 268 ms 46348 KB Output is correct
13 Correct 286 ms 48480 KB Output is correct
14 Correct 264 ms 43848 KB Output is correct
15 Correct 38 ms 18592 KB Output is correct
16 Correct 451 ms 39076 KB Output is correct
17 Correct 270 ms 40112 KB Output is correct
18 Correct 411 ms 35884 KB Output is correct
19 Correct 416 ms 47756 KB Output is correct
20 Correct 403 ms 52300 KB Output is correct
21 Correct 368 ms 40780 KB Output is correct
22 Correct 351 ms 41520 KB Output is correct