oj.uz

Submission #384843

# Submission time Handle Problem Language Result Execution time Memory
384843 2021-04-02T12:35:45 Z dolphingarlic Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 107448 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<int> graph[500001];
int sheep[500001], to_sheep[500001], depth[500001], anc[500001][19], highest[500001];
bool guarded[500001];

void dfs(int node = 1, int parent = 0, int d = 0) {
    depth[node] = d;
    for (int i = 1; i < 19; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];

    int h = node, dist = 1;
    for (int i = 18; ~i; i--) if (dist + (1 << i) == to_sheep[anc[h][i]]) {
        dist += (1 << i);
        h = anc[h][i];
    }
    highest[node] = h;

    for (int i : graph[node]) if (i != parent) {
        anc[i][0] = node;
        dfs(i, node, d + 1);
    }
}

void guard(int node) {
    guarded[node] = true;
    for (int i : graph[node]) if (!guarded[i] && to_sheep[node] == to_sheep[i] + 1) guard(i);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    queue<int> q;
    for (int i = 1; i <= k; i++) {
        cin >> sheep[i];
        q.push(sheep[i]);
        to_sheep[sheep[i]] = 1;
    }
    while (q.size()) {
        int curr = q.front();
        q.pop();
        for (int i : graph[curr]) if (!to_sheep[i]) {
            to_sheep[i] = to_sheep[curr] + 1;
            q.push(i);
        }
    }
    dfs();

    vector<int> ans;
    sort(sheep + 1, sheep + k + 1, [](int A, int B) { return depth[A] > depth[B]; });
    for (int i = 1; i <= k; i++) if (!guarded[sheep[i]]) {
        int node = highest[sheep[i]];
        ans.push_back(node);
        guard(node);
    }
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 102252 KB Output is correct
2 Correct 411 ms 102636 KB Output is correct
3 Correct 411 ms 102636 KB Output is correct
4 Correct 509 ms 107448 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12780 KB Output is correct
2 Correct 12 ms 12652 KB Output is correct
3 Correct 695 ms 71788 KB Output is correct
4 Correct 687 ms 74220 KB Output is correct
5 Correct 944 ms 71404 KB Output is correct
6 Execution timed out 1097 ms 73708 KB Time limit exceeded

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12396 KB Output is correct
2 Correct 10 ms 12396 KB Output is correct
3 Correct 13 ms 12524 KB Output is correct
4 Correct 11 ms 12268 KB Output is correct
5 Correct 10 ms 12396 KB Output is correct
6 Correct 11 ms 12396 KB Output is correct
7 Correct 10 ms 12396 KB Output is correct
8 Correct 11 ms 12396 KB Output is correct
9 Correct 10 ms 12396 KB Output is correct
10 Correct 10 ms 12396 KB Output is correct
11 Correct 10 ms 12268 KB Output is correct
12 Correct 10 ms 12268 KB Output is correct
13 Correct 10 ms 12396 KB Output is correct
14 Correct 11 ms 12396 KB Output is correct
15 Correct 10 ms 12396 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 72348 KB Output is correct
2 Correct 869 ms 72300 KB Output is correct
3 Correct 848 ms 74332 KB Output is correct
4 Correct 901 ms 71276 KB Output is correct
5 Correct 657 ms 62692 KB Output is correct
6 Correct 983 ms 78388 KB Output is correct
7 Execution timed out 1018 ms 76908 KB Time limit exceeded
8 Halted 0 ms 0 KB -