oj.uz

Submission #467354

# Submission time Handle Problem Language Result Execution time Memory
467354 2021-08-22T17:53:47 Z phathnv Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 194744 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500007;

int n, k, sheep[N], h[N], d[N], trace[N], numNode;
pair<int, int> best[2 * N];
vector<int> adj[N], child[2 * N];
bool vst[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;
        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] = trace[u];
                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]);
                trace[v] = newNode;
            }
        }
    }
    for (int u = 1; u <= numNode; u++) {
        if (u <= k)
            best[u] = {h[sheep[u]], 0};
        else
            best[u] = {1e9, 0};
        for (int v : child[u]) {
            best[u] = min(best[u], best[v]);
            vst[v] = true;
        }
        best[u].second = u;
    }
    for (int u = 1; u <= numNode; u++)
        if (vst[u]) {
            best[u] = {1e9, 1e9};
            vst[u] = false;
        }
    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]];
         });
    map<int, int> nodeToVex;
    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:101:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  101 |     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 257 ms 56972 KB Output is correct
2 Correct 289 ms 57156 KB Output is correct
3 Correct 257 ms 57136 KB Output is correct
4 Correct 880 ms 86416 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35788 KB Output is correct
2 Correct 22 ms 35788 KB Output is correct
3 Correct 541 ms 57700 KB Output is correct
4 Correct 505 ms 60484 KB Output is correct
5 Correct 626 ms 56956 KB Output is correct
6 Correct 647 ms 57172 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35660 KB Output is correct
2 Correct 20 ms 35612 KB Output is correct
3 Correct 20 ms 35660 KB Output is correct
4 Correct 24 ms 35688 KB Output is correct
5 Correct 22 ms 35688 KB Output is correct
6 Correct 21 ms 35772 KB Output is correct
7 Correct 20 ms 35652 KB Output is correct
8 Correct 21 ms 35660 KB Output is correct
9 Correct 20 ms 35648 KB Output is correct
10 Correct 21 ms 35668 KB Output is correct
11 Correct 19 ms 35604 KB Output is correct
12 Correct 21 ms 35796 KB Output is correct
13 Correct 22 ms 35676 KB Output is correct
14 Correct 21 ms 35656 KB Output is correct
15 Correct 22 ms 35660 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 58780 KB Output is correct
2 Correct 628 ms 58744 KB Output is correct
3 Correct 990 ms 85444 KB Output is correct
4 Correct 673 ms 63840 KB Output is correct
5 Correct 761 ms 86336 KB Output is correct
6 Execution timed out 1010 ms 194744 KB Time limit exceeded
7 Halted 0 ms 0 KB -