oj.uz

Submission #384844

# Submission time Handle Problem Language Result Execution time Memory
384844 2021-04-02T12:43:09 Z dolphingarlic Pastiri (COI20_pastiri) C++14
100 / 100
 969 ms 108088 KB 
/*
COI 2020 Pastiri
- First, root the tree
- For each sheep, find the highest node a shepherd can be at while guarding it
    - We first do multi-source BFS to find the closest sheep to each node, and
      then binary lifting to find the answer
- Let's process the sheep in order of their depths (greatest depth first)
- It's optimal to greedily assign shepherds to the highest nodes for each
  unguarded sheep as we go through the list
- We can then use DFS to mark sheep as guarded
- Complexity: O(N + K log N)
*/

#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 has_sheep[500001], 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;
    if (has_sheep[node])
        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];
        has_sheep[sheep[i]] = true;
        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 285 ms 102156 KB Output is correct
2 Correct 320 ms 103196 KB Output is correct
3 Correct 315 ms 103148 KB Output is correct
4 Correct 475 ms 108088 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12780 KB Output is correct
2 Correct 11 ms 12716 KB Output is correct
3 Correct 606 ms 71788 KB Output is correct
4 Correct 610 ms 74140 KB Output is correct
5 Correct 800 ms 71404 KB Output is correct
6 Correct 940 ms 74220 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12396 KB Output is correct
2 Correct 9 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 10 ms 12396 KB Output is correct
7 Correct 12 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 9 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
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 72940 KB Output is correct
2 Correct 750 ms 72780 KB Output is correct
3 Correct 801 ms 74856 KB Output is correct
4 Correct 788 ms 71772 KB Output is correct
5 Correct 643 ms 63180 KB Output is correct
6 Correct 913 ms 78880 KB Output is correct
7 Correct 940 ms 77292 KB Output is correct
8 Correct 909 ms 77036 KB Output is correct
9 Correct 912 ms 72032 KB Output is correct
10 Correct 785 ms 78060 KB Output is correct
11 Correct 607 ms 80520 KB Output is correct
12 Correct 568 ms 84320 KB Output is correct
13 Correct 652 ms 86620 KB Output is correct
14 Correct 540 ms 82188 KB Output is correct
15 Correct 96 ms 23276 KB Output is correct
16 Correct 790 ms 73452 KB Output is correct
17 Correct 576 ms 70240 KB Output is correct
18 Correct 712 ms 66668 KB Output is correct
19 Correct 885 ms 84460 KB Output is correct
20 Correct 969 ms 88172 KB Output is correct
21 Correct 730 ms 78588 KB Output is correct
22 Correct 762 ms 79248 KB Output is correct