oj.uz

Submission #467335

# Submission time Handle Problem Language Result Execution time Memory
467335 2021-08-22T16:23:51 Z phathnv Pastiri (COI20_pastiri) C++11
0 / 100
 802 ms 63384 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500007;

int n, k, d[N], trace[N], numNode;
vector<int> adj[N], sheep, child[2 * N];
bool vst[N];

int main() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    sheep.assign(k, 0);
    for (int &x : sheep)
        cin >> x;
    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    queue<int> qu;
    for (int x : sheep) {
        d[x] = 0;
        trace[x] = ++numNode;
        qu.push(x);
    }
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int v : adj[u]) {
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                trace[v] = trace[u];
                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;
            }
        }
    }
    map<int, int> nodeToVex;
    for (int i = 1; i <= n; i++)
        nodeToVex[trace[i]] = i;
    vector<int> answer;
    for (int i = 1; i <= numNode; i++)
        for (int v : child[i])
            vst[v] = true;
    for (int i = 1; i <= numNode; i++)
        if (!vst[i])
            answer.push_back(nodeToVex[i]);
    cout << answer.size() << '\n';
    for (int x : answer)
        cout << x << ' ';
    cout << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 61712 KB Output is correct
2 Incorrect 481 ms 61764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 35708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 35564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 802 ms 63384 KB Output isn't correct
2 Halted 0 ms 0 KB -