oj.uz

Submission #1093116

# Submission time Handle Problem Language Result Execution time Memory
1093116 2024-09-26T01:30:04 Z ShadowShark Pastiri (COI20_pastiri) C++17
100 / 100
 474 ms 117172 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e5 + 5;
int depth[maxN], dis[maxN], par[20][maxN], done[maxN];
bool visited[maxN];
vector<int> adj[maxN];
vector<pair<int, int>> order;

void dfs(int u, int pre) {
    for (auto v: adj[u]) {
        if (v == pre) continue;
        depth[v] = depth[u] + 1;
        par[0][v] = u;
        dfs(v, u);
    }
}

void bfs() {
    queue<int> Q;
    for (auto it: order) {
        visited[it.second] = true;
        Q.push(it.second);
    }

    while (Q.size() > 0) {
        int u = Q.front(); Q.pop();
        for (auto v: adj[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            dis[v] = dis[u] + 1;
            Q.push(v);
        }
    }
}

bool cmp(pair<int, int> A, pair<int, int> B) {
    return A.first > B.first;
}

void mark_done(int u) {
    done[u] = 1;
    for (auto v: adj[u]) {
        if (done[v]) continue;
        if (dis[v] + 1 != dis[u]) continue;
        mark_done(v);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;
    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);
    }

    depth[1] = 1;
    dfs(1, 1);

    for (int j = 1; j <= 18; j++)
        for (int i = 1; i <= n; i++)
            par[j][i] = par[j - 1][par[j - 1][i]];

    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;

        order.push_back({depth[x], x});
    }

    bfs();
    sort(order.begin(), order.end(), cmp);

    //for (int i = 1; i <= n; i++)
        //cout << dis[i] << ' ';
    //cout << '\n';

    vector<int> ans;
    for (auto it: order) {
        int u = it.second;
        if (done[u]) continue;

        int x = u;
        for (int j = 18; j >= 0; j--) {
            int v = par[j][x];
            if (v != 0 && depth[u] - depth[v] == dis[v]) x = v;
        }

        //cout << u << ' ' << x << '\n';
        mark_done(x);

        //for (int i = 1; i <= n; i++)
            //cout << done[i] << ' ';
        //cout << '\n';

        ans.push_back(x);
    }

    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto v: ans)
        if (v != ans.back()) cout << v << ' ';
            else cout << v;

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 100944 KB Output is correct
2 Correct 184 ms 108884 KB Output is correct
3 Correct 170 ms 109140 KB Output is correct
4 Correct 286 ms 117172 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12892 KB Output is correct
2 Correct 7 ms 12896 KB Output is correct
3 Correct 254 ms 76868 KB Output is correct
4 Correct 242 ms 79056 KB Output is correct
5 Correct 318 ms 77908 KB Output is correct
6 Correct 422 ms 80724 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12376 KB Output is correct
2 Correct 6 ms 12632 KB Output is correct
3 Correct 6 ms 12476 KB Output is correct
4 Correct 5 ms 12460 KB Output is correct
5 Correct 6 ms 12640 KB Output is correct
6 Correct 6 ms 12636 KB Output is correct
7 Correct 6 ms 12384 KB Output is correct
8 Correct 6 ms 12384 KB Output is correct
9 Correct 6 ms 12476 KB Output is correct
10 Correct 5 ms 12636 KB Output is correct
11 Correct 6 ms 12380 KB Output is correct
12 Correct 6 ms 12360 KB Output is correct
13 Correct 7 ms 12624 KB Output is correct
14 Correct 6 ms 12636 KB Output is correct
15 Correct 6 ms 12632 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 72252 KB Output is correct
2 Correct 305 ms 78932 KB Output is correct
3 Correct 399 ms 82772 KB Output is correct
4 Correct 306 ms 78160 KB Output is correct
5 Correct 274 ms 69960 KB Output is correct
6 Correct 379 ms 88252 KB Output is correct
7 Correct 432 ms 85700 KB Output is correct
8 Correct 384 ms 85184 KB Output is correct
9 Correct 358 ms 78124 KB Output is correct
10 Correct 273 ms 77904 KB Output is correct
11 Correct 210 ms 79956 KB Output is correct
12 Correct 250 ms 84668 KB Output is correct
13 Correct 263 ms 86940 KB Output is correct
14 Correct 209 ms 81192 KB Output is correct
15 Correct 39 ms 23516 KB Output is correct
16 Correct 422 ms 72996 KB Output is correct
17 Correct 364 ms 70464 KB Output is correct
18 Correct 368 ms 66272 KB Output is correct
19 Correct 464 ms 84196 KB Output is correct
20 Correct 474 ms 87488 KB Output is correct
21 Correct 368 ms 78044 KB Output is correct
22 Correct 354 ms 78592 KB Output is correct