oj.uz

Submission #467363

# Submission time Handle Problem Language Result Execution time Memory
467363 2021-08-22T17:59:28 Z phathnv Pastiri (COI20_pastiri) C++11
100 / 100
 813 ms 88272 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500007;

int n, k, sheep[N], h[N], d[N], trace[N], numNode, nodeToVex[2 * N];
pair<int, int> best[2 * N];
vector<int> adj[N], child[2 * N];
bool vst[2 * N];

int main() {
    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 = 1; i <= k; i++)
        scanf("%d", &sheep[i]);
    queue<int> qu;
    h[1] = 1;
    qu.push(1);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : adj[u])
            if (!h[v]) {
                h[v] = h[u] + 1;
                qu.push(v);
            }
    }
    for (int i = 1; i <= k; i++) {
        int x = sheep[i];
        ++numNode;
        best[numNode] = {h[x], numNode};
        trace[x] = numNode;
        d[x] = 1;
        qu.push(x);
    }
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : adj[u]) {
            if (!d[v]) {
                trace[v] = best[trace[u]].second;
                d[v] = d[u] + 1;
                qu.push(v);
            } else if (d[v] == d[u] + 1) {
                int newNode = ++numNode;
                child[newNode].push_back(trace[u]);
                child[newNode].push_back(trace[v]);
                best[newNode] = {min(best[trace[u]].first, best[trace[v]].first), newNode};
                vst[trace[u]] = vst[trace[v]] = true;
                trace[v] = newNode;
            }
        }
    }
    for (int u = 1; u <= numNode; u++)
        if (vst[u]) {
            vst[u] = false;
            best[u] = {1e9, 1e9};
        }
    for (int u = numNode; u >= 1; u--) {
        for (int v : child[u])
            best[v] = min(best[v], best[u]);
    }
    vector<int> ord(k);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](const int &a, const int &b){
            return h[sheep[a]] > h[sheep[b]];
         });
    for (int i = 1; i <= n; i++)
        nodeToVex[trace[i]] = i;
    vector<int> answer;
    for (int x : ord) {
        if (vst[x])
            continue;
        queue<int> qu;
        qu.push(best[x].second);
        answer.push_back(nodeToVex[best[x].second]);
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            if (vst[u])
                continue;
            vst[u] = true;
            for (int v : child[u])
                qu.push(v);
        }
    }
    printf("%d\n", answer.size());
    for (int x : answer)
        printf("%d ", x);
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 56992 KB Output is correct
2 Correct 248 ms 57052 KB Output is correct
3 Correct 246 ms 57028 KB Output is correct
4 Correct 461 ms 69820 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35668 KB Output is correct
2 Correct 22 ms 35720 KB Output is correct
3 Correct 494 ms 57628 KB Output is correct
4 Correct 504 ms 60472 KB Output is correct
5 Correct 604 ms 57032 KB Output is correct
6 Correct 617 ms 57152 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35660 KB Output is correct
2 Correct 22 ms 35596 KB Output is correct
3 Correct 22 ms 35724 KB Output is correct
4 Correct 20 ms 35588 KB Output is correct
5 Correct 21 ms 35636 KB Output is correct
6 Correct 21 ms 35724 KB Output is correct
7 Correct 22 ms 35652 KB Output is correct
8 Correct 20 ms 35620 KB Output is correct
9 Correct 21 ms 35576 KB Output is correct
10 Correct 21 ms 35668 KB Output is correct
11 Correct 21 ms 35660 KB Output is correct
12 Correct 20 ms 35692 KB Output is correct
13 Correct 20 ms 35628 KB Output is correct
14 Correct 21 ms 35628 KB Output is correct
15 Correct 21 ms 35652 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 57988 KB Output is correct
2 Correct 532 ms 58020 KB Output is correct
3 Correct 709 ms 71560 KB Output is correct
4 Correct 633 ms 57080 KB Output is correct
5 Correct 525 ms 66868 KB Output is correct
6 Correct 813 ms 78448 KB Output is correct
7 Correct 767 ms 82080 KB Output is correct
8 Correct 730 ms 79484 KB Output is correct
9 Correct 691 ms 63760 KB Output is correct
10 Correct 592 ms 63684 KB Output is correct
11 Correct 453 ms 66340 KB Output is correct
12 Correct 521 ms 81220 KB Output is correct
13 Correct 649 ms 88272 KB Output is correct
14 Correct 413 ms 67832 KB Output is correct
15 Correct 77 ms 41548 KB Output is correct
16 Correct 556 ms 63008 KB Output is correct
17 Correct 488 ms 74520 KB Output is correct
18 Correct 488 ms 58632 KB Output is correct
19 Correct 612 ms 70196 KB Output is correct
20 Correct 607 ms 67324 KB Output is correct
21 Correct 560 ms 63956 KB Output is correct
22 Correct 597 ms 64080 KB Output is correct