oj.uz

답안 #467362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467362 2021-08-22T17:58:41 Z phathnv Pastiri (COI20_pastiri) C++11
49 / 100
 767 ms 78016 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500007;

int n, k, sheep[N], h[N], d[N], trace[N], numNode, nodeToVex[N];
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]];
         });
    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:92:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 57152 KB Output is correct
2 Correct 251 ms 57216 KB Output is correct
3 Correct 238 ms 56988 KB Output is correct
4 Correct 488 ms 69888 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 35788 KB Output is correct
2 Correct 22 ms 35788 KB Output is correct
3 Correct 527 ms 57644 KB Output is correct
4 Correct 482 ms 60504 KB Output is correct
5 Correct 609 ms 57004 KB Output is correct
6 Correct 595 ms 56940 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35660 KB Output is correct
2 Correct 21 ms 35580 KB Output is correct
3 Correct 20 ms 35660 KB Output is correct
4 Correct 21 ms 35612 KB Output is correct
5 Correct 21 ms 35684 KB Output is correct
6 Correct 21 ms 35728 KB Output is correct
7 Correct 20 ms 35660 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 20 ms 35660 KB Output is correct
10 Correct 21 ms 35620 KB Output is correct
11 Correct 24 ms 35660 KB Output is correct
12 Correct 20 ms 35604 KB Output is correct
13 Correct 23 ms 35696 KB Output is correct
14 Correct 20 ms 35660 KB Output is correct
15 Correct 21 ms 35596 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 57892 KB Output is correct
2 Correct 563 ms 58032 KB Output is correct
3 Correct 717 ms 71520 KB Output is correct
4 Correct 612 ms 57172 KB Output is correct
5 Correct 577 ms 66924 KB Output is correct
6 Incorrect 767 ms 78016 KB Integer 0 violates the range [1, 500000]
7 Halted 0 ms 0 KB -