oj.uz

Submission #467347

# Submission time Handle Problem Language Result Execution time Memory
467347 2021-08-22T17:41:39 Z phathnv Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 86432 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;
        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]];
         });
    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:93:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   93 |     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 204 ms 56960 KB Output is correct
2 Correct 256 ms 57156 KB Output is correct
3 Correct 253 ms 57028 KB Output is correct
4 Correct 860 ms 86432 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35660 KB Output is correct
2 Correct 22 ms 35836 KB Output is correct
3 Correct 501 ms 57620 KB Output is correct
4 Correct 551 ms 60548 KB Output is correct
5 Correct 598 ms 57036 KB Output is correct
6 Correct 596 ms 56972 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 20 ms 35632 KB Output is correct
3 Correct 22 ms 35700 KB Output is correct
4 Correct 21 ms 35668 KB Output is correct
5 Correct 21 ms 35652 KB Output is correct
6 Correct 23 ms 35780 KB Output is correct
7 Correct 21 ms 35532 KB Output is correct
8 Correct 23 ms 35580 KB Output is correct
9 Correct 20 ms 35688 KB Output is correct
10 Correct 21 ms 35760 KB Output is correct
11 Correct 25 ms 35604 KB Output is correct
12 Correct 21 ms 35660 KB Output is correct
13 Correct 21 ms 35652 KB Output is correct
14 Correct 22 ms 35660 KB Output is correct
15 Correct 21 ms 35696 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 58696 KB Output is correct
2 Correct 620 ms 58876 KB Output is correct
3 Execution timed out 1037 ms 85428 KB Time limit exceeded
4 Halted 0 ms 0 KB -