oj.uz

Submission #312533

# Submission time Handle Problem Language Result Execution time Memory
312533 2020-10-13T16:40:43 Z model_code Pastiri (COI20_pastiri) C++17
100 / 100
 832 ms 77068 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 243 ms 72952 KB Output is correct
2 Correct 279 ms 73336 KB Output is correct
3 Correct 274 ms 73336 KB Output is correct
4 Correct 386 ms 77068 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14208 KB Output is correct
2 Correct 11 ms 14208 KB Output is correct
3 Correct 547 ms 34000 KB Output is correct
4 Correct 538 ms 36432 KB Output is correct
5 Correct 676 ms 34264 KB Output is correct
6 Correct 797 ms 37912 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 35240 KB Output is correct
2 Correct 634 ms 35156 KB Output is correct
3 Correct 732 ms 36304 KB Output is correct
4 Correct 673 ms 34168 KB Output is correct
5 Correct 534 ms 32496 KB Output is correct
6 Correct 706 ms 41116 KB Output is correct
7 Correct 821 ms 39312 KB Output is correct
8 Correct 749 ms 39112 KB Output is correct
9 Correct 832 ms 34168 KB Output is correct
10 Correct 744 ms 34212 KB Output is correct
11 Correct 555 ms 35624 KB Output is correct
12 Correct 534 ms 37784 KB Output is correct
13 Correct 585 ms 38828 KB Output is correct
14 Correct 517 ms 37052 KB Output is correct
15 Correct 90 ms 17528 KB Output is correct
16 Correct 767 ms 32760 KB Output is correct
17 Correct 537 ms 33204 KB Output is correct
18 Correct 657 ms 30580 KB Output is correct
19 Correct 694 ms 40316 KB Output is correct
20 Correct 735 ms 45356 KB Output is correct
21 Correct 631 ms 34200 KB Output is correct
22 Correct 638 ms 35036 KB Output is correct