oj.uz

Submission #467346

# Submission time Handle Problem Language Result Execution time Memory
467346 2021-08-22T17:40:13 Z phathnv Pastiri (COI20_pastiri) C++17
41 / 100
 1000 ms 84864 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() {
    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);
    }
    for (int i = 1; i <= k; i++)
        cin >> 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]];
         });
    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);
        }
    }
    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 486 ms 57056 KB Output is correct
2 Correct 484 ms 57156 KB Output is correct
3 Correct 517 ms 57092 KB Output is correct
4 Execution timed out 1099 ms 84864 KB Time limit exceeded

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35788 KB Output is correct
2 Correct 23 ms 35780 KB Output is correct
3 Correct 753 ms 57644 KB Output is correct
4 Correct 732 ms 60548 KB Output is correct
5 Correct 849 ms 57024 KB Output is correct
6 Correct 859 ms 57032 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35660 KB Output is correct
2 Correct 25 ms 35616 KB Output is correct
3 Correct 21 ms 35660 KB Output is correct
4 Correct 21 ms 35660 KB Output is correct
5 Correct 22 ms 35764 KB Output is correct
6 Correct 22 ms 35736 KB Output is correct
7 Correct 25 ms 35660 KB Output is correct
8 Correct 24 ms 35660 KB Output is correct
9 Correct 25 ms 35568 KB Output is correct
10 Correct 22 ms 35660 KB Output is correct
11 Correct 24 ms 35660 KB Output is correct
12 Correct 22 ms 35660 KB Output is correct
13 Correct 22 ms 35764 KB Output is correct
14 Correct 21 ms 35660 KB Output is correct
15 Correct 22 ms 35644 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 58680 KB Output is correct
2 Correct 853 ms 58764 KB Output is correct
3 Execution timed out 1080 ms 83780 KB Time limit exceeded
4 Halted 0 ms 0 KB -