oj.uz

Submission #467355

# Submission time Handle Problem Language Result Execution time Memory
467355 2021-08-22T17:54:20 Z phathnv Pastiri (COI20_pastiri) C++
49 / 100
 1000 ms 86324 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 209 ms 57068 KB Output is correct
2 Correct 251 ms 57120 KB Output is correct
3 Correct 260 ms 57028 KB Output is correct
4 Correct 879 ms 86324 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 24 ms 35780 KB Output is correct
3 Correct 540 ms 57660 KB Output is correct
4 Correct 531 ms 60568 KB Output is correct
5 Correct 633 ms 57032 KB Output is correct
6 Correct 587 ms 56944 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35576 KB Output is correct
2 Correct 21 ms 35660 KB Output is correct
3 Correct 20 ms 35724 KB Output is correct
4 Correct 22 ms 35684 KB Output is correct
5 Correct 26 ms 35788 KB Output is correct
6 Correct 20 ms 35660 KB Output is correct
7 Correct 21 ms 35624 KB Output is correct
8 Correct 24 ms 35548 KB Output is correct
9 Correct 21 ms 35580 KB Output is correct
10 Correct 21 ms 35684 KB Output is correct
11 Correct 20 ms 35660 KB Output is correct
12 Correct 21 ms 35652 KB Output is correct
13 Correct 22 ms 35740 KB Output is correct
14 Correct 21 ms 35660 KB Output is correct
15 Correct 21 ms 35736 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 58688 KB Output is correct
2 Correct 691 ms 58792 KB Output is correct
3 Execution timed out 1070 ms 85364 KB Time limit exceeded
4 Halted 0 ms 0 KB -