oj.uz

Submission #467345

# Submission time Handle Problem Language Result Execution time Memory
467345 2021-08-22T17:39:29 Z phathnv Pastiri (COI20_pastiri) C++11
41 / 100
 1000 ms 93396 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 444 ms 57028 KB Output is correct
2 Correct 559 ms 57220 KB Output is correct
3 Correct 503 ms 63740 KB Output is correct
4 Execution timed out 1090 ms 93396 KB Time limit exceeded

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35684 KB Output is correct
2 Correct 24 ms 35736 KB Output is correct
3 Correct 734 ms 64368 KB Output is correct
4 Correct 741 ms 67128 KB Output is correct
5 Correct 849 ms 63672 KB Output is correct
6 Correct 823 ms 63688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35660 KB Output is correct
2 Correct 21 ms 35672 KB Output is correct
3 Correct 22 ms 35788 KB Output is correct
4 Correct 23 ms 35672 KB Output is correct
5 Correct 23 ms 35740 KB Output is correct
6 Correct 22 ms 35800 KB Output is correct
7 Correct 22 ms 35676 KB Output is correct
8 Correct 26 ms 35672 KB Output is correct
9 Correct 22 ms 35660 KB Output is correct
10 Correct 21 ms 35676 KB Output is correct
11 Correct 21 ms 35680 KB Output is correct
12 Correct 22 ms 35636 KB Output is correct
13 Correct 22 ms 35788 KB Output is correct
14 Correct 22 ms 35672 KB Output is correct
15 Correct 22 ms 35768 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 58764 KB Output is correct
2 Correct 882 ms 65568 KB Output is correct
3 Execution timed out 1096 ms 90916 KB Time limit exceeded
4 Halted 0 ms 0 KB -