oj.uz

Submission #467361

# Submission time Handle Problem Language Result Execution time Memory
467361 2021-08-22T17:58:02 Z phathnv Pastiri (COI20_pastiri) C++11
49 / 100
 1000 ms 86428 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[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]];
         });
    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 214 ms 57028 KB Output is correct
2 Correct 249 ms 57156 KB Output is correct
3 Correct 293 ms 57048 KB Output is correct
4 Correct 882 ms 86428 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35788 KB Output is correct
2 Correct 22 ms 35788 KB Output is correct
3 Correct 483 ms 57704 KB Output is correct
4 Correct 502 ms 60572 KB Output is correct
5 Correct 606 ms 56960 KB Output is correct
6 Correct 610 ms 56968 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 21 ms 35556 KB Output is correct
3 Correct 21 ms 35660 KB Output is correct
4 Correct 20 ms 35716 KB Output is correct
5 Correct 20 ms 35788 KB Output is correct
6 Correct 23 ms 35772 KB Output is correct
7 Correct 20 ms 35660 KB Output is correct
8 Correct 20 ms 35632 KB Output is correct
9 Correct 20 ms 35660 KB Output is correct
10 Correct 23 ms 35660 KB Output is correct
11 Correct 19 ms 35700 KB Output is correct
12 Correct 20 ms 35660 KB Output is correct
13 Correct 21 ms 35660 KB Output is correct
14 Correct 21 ms 35612 KB Output is correct
15 Correct 21 ms 35656 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 58788 KB Output is correct
2 Correct 631 ms 58792 KB Output is correct
3 Execution timed out 1092 ms 85420 KB Time limit exceeded
4 Halted 0 ms 0 KB -