oj.uz

Submission #1093113

# Submission time Handle Problem Language Result Execution time Memory
1093113 2024-09-26T01:22:02 Z ShadowShark Pastiri (COI20_pastiri) C++17
0 / 100
 366 ms 108888 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(u);
        }
    }
}

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 (v == par[0][u] || done[v]) 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);

    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;
        }

        mark_done(x);
        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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 106516 KB Output is correct
2 Incorrect 143 ms 108888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 366 ms 78920 KB Output isn't correct
2 Halted 0 ms 0 KB -