oj.uz

Submission #678777

# Submission time Handle Problem Language Result Execution time Memory
678777 2023-01-06T14:19:06 Z Cyanmond Pastiri (COI20_pastiri) C++17
100 / 100
 845 ms 67764 KB 
#include <bits/stdc++.h>

constexpr int inf = 100000000;

int main() {
    int N, K;
    std::cin >> N >> K;
    std::vector<int> A(N - 1), B(N - 1), O(K);
    std::vector<std::vector<int>> tree(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        tree[A[i]].push_back(B[i]);
        tree[B[i]].push_back(A[i]);
    }
    for (auto &e : O) {
        std::cin >> e;
        --e;
    }

    std::queue<int> que;
    std::vector<int> dist(N, -1);
    for (const int e : O) {
        que.push(e);
        dist[e] = 0;
    }
    while (not que.empty()) {
        const int f = que.front();
        que.pop();
        for (const int t : tree[f]) {
            if (dist[t] == -1) {
                dist[t] = dist[f] + 1;
                que.push(t);
            }
        }
    }

    std::vector<int> depth(N), ac(N);
    auto dfs = [&](auto &&self, const int v, const int p, const int d, int h) -> void {
        depth[v] = d;
        if (depth[v] + dist[v] > depth[h] + dist[h]) {
            h = v;
        }
        ac[v] = h;
        for (const int t : tree[v]) {
            if (t == p) {
                continue;
            }
            self(self, t, v, d + 1, h);
        }
    };
    dfs(dfs, 0, -1, 0, 0);

    std::sort(O.begin(), O.end(), [&](const int a, const int b) {
        return depth[a] > depth[b];
    });
    
    std::vector<bool> seen(N);
    std::vector<int> answer;
    for (int i = 0; i < K; ++i) {
        if (seen[O[i]]) {
            continue;
        }
        que.push(ac[O[i]]);
        seen[ac[O[i]]] = true;
        answer.push_back(ac[O[i]]);
        while (not que.empty()) {
            const int f = que.front();
            que.pop();
            for (const int t : tree[f]) {
                if (seen[t]) {
                    continue;
                }
                if (dist[t] + 1 == dist[f]) {
                    seen[t] = true;
                    que.push(t);
                }
            }
        }
    }

    std::sort(answer.begin(), answer.end());
    std::cout << answer.size() << std::endl;
    for (int i = 0; i < (int)answer.size(); ++i) {
        std::cout << answer[i] + 1;
        std::cout << (i == (int)answer.size() - 1 ? '\n' : ' ');
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 62988 KB Output is correct
2 Correct 375 ms 63096 KB Output is correct
3 Correct 386 ms 62940 KB Output is correct
4 Correct 509 ms 67764 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 692 KB Output is correct
2 Correct 4 ms 696 KB Output is correct
3 Correct 614 ms 44660 KB Output is correct
4 Correct 609 ms 46956 KB Output is correct
5 Correct 720 ms 44132 KB Output is correct
6 Correct 845 ms 45892 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 440 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 408 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 436 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 44632 KB Output is correct
2 Correct 685 ms 44892 KB Output is correct
3 Correct 750 ms 48388 KB Output is correct
4 Correct 693 ms 44156 KB Output is correct
5 Correct 610 ms 39856 KB Output is correct
6 Correct 763 ms 51824 KB Output is correct
7 Correct 790 ms 50348 KB Output is correct
8 Correct 799 ms 49904 KB Output is correct
9 Correct 817 ms 44328 KB Output is correct
10 Correct 699 ms 44104 KB Output is correct
11 Correct 552 ms 46148 KB Output is correct
12 Correct 557 ms 49828 KB Output is correct
13 Correct 632 ms 51960 KB Output is correct
14 Correct 508 ms 47748 KB Output is correct
15 Correct 79 ms 7752 KB Output is correct
16 Correct 776 ms 41032 KB Output is correct
17 Correct 563 ms 40292 KB Output is correct
18 Correct 641 ms 36168 KB Output is correct
19 Correct 705 ms 48452 KB Output is correct
20 Correct 701 ms 50368 KB Output is correct
21 Correct 648 ms 44332 KB Output is correct
22 Correct 645 ms 44744 KB Output is correct