oj.uz

Submission #384842

# Submission time Handle Problem Language Result Execution time Memory
384842 2021-04-02T12:33:58 Z dolphingarlic Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 107564 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 359 ms 102400 KB Output is correct
2 Correct 409 ms 102592 KB Output is correct
3 Correct 415 ms 102636 KB Output is correct
4 Correct 505 ms 107564 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 692 ms 71876 KB Output is correct
4 Correct 672 ms 73964 KB Output is correct
5 Correct 950 ms 71404 KB Output is correct
6 Execution timed out 1098 ms 80236 KB Time limit exceeded

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12396 KB Output is correct
2 Correct 10 ms 12396 KB Output is correct
3 Correct 10 ms 12396 KB Output is correct
4 Correct 10 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 10 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 10 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 854 ms 72424 KB Output is correct
2 Correct 859 ms 72420 KB Output is correct
3 Correct 831 ms 74356 KB Output is correct
4 Correct 870 ms 71276 KB Output is correct
5 Correct 633 ms 62692 KB Output is correct
6 Correct 963 ms 78388 KB Output is correct
7 Correct 988 ms 76908 KB Output is correct
8 Correct 993 ms 84460 KB Output is correct
9 Execution timed out 1052 ms 78060 KB Time limit exceeded
10 Halted 0 ms 0 KB -