oj.uz

Submission #467360

# Submission time Handle Problem Language Result Execution time Memory
467360 2021-08-22T17:56:53 Z phathnv Pastiri (COI20_pastiri) C++
49 / 100
 1000 ms 87424 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<pair<int, int>> ord(k);
    for (int i = 1; i <= k; i++)
        ord[i - 1] = {-h[sheep[i]], i};
    sort(ord.begin(), ord.end());
    map<int, int> nodeToVex;
    for (int i = 1; i <= n; i++)
        nodeToVex[trace[i]] = i;
    vector<int> answer;
    for (auto p : ord) {
        int x = p.second;
        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 207 ms 57008 KB Output is correct
2 Correct 259 ms 57296 KB Output is correct
3 Correct 258 ms 57084 KB Output is correct
4 Correct 910 ms 87424 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35788 KB Output is correct
2 Correct 22 ms 35668 KB Output is correct
3 Correct 552 ms 57668 KB Output is correct
4 Correct 546 ms 60528 KB Output is correct
5 Correct 676 ms 57080 KB Output is correct
6 Correct 623 ms 57044 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35684 KB Output is correct
2 Correct 22 ms 35636 KB Output is correct
3 Correct 25 ms 35660 KB Output is correct
4 Correct 23 ms 35616 KB Output is correct
5 Correct 21 ms 35788 KB Output is correct
6 Correct 21 ms 35660 KB Output is correct
7 Correct 21 ms 35652 KB Output is correct
8 Correct 22 ms 35644 KB Output is correct
9 Correct 24 ms 35608 KB Output is correct
10 Correct 21 ms 35684 KB Output is correct
11 Correct 22 ms 35712 KB Output is correct
12 Correct 23 ms 35696 KB Output is correct
13 Correct 21 ms 35660 KB Output is correct
14 Correct 20 ms 35704 KB Output is correct
15 Correct 21 ms 35660 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 58756 KB Output is correct
2 Correct 656 ms 58820 KB Output is correct
3 Execution timed out 1050 ms 86220 KB Time limit exceeded
4 Halted 0 ms 0 KB -