oj.uz

Submission #1004130

# Submission time Handle Problem Language Result Execution time Memory
1004130 2024-06-21T05:39:45 Z vjudge1 Pastiri (COI20_pastiri) C++17
26 / 100
 565 ms 101496 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int n, k, a[N], par[N], h[N];
vector<int> g[N];
// set<int> poss[N];

bool mark[N];
map<int, bool> exist;
vector<int> dist2(N, N + 10);

vector<int> bfs(vector<int> sources){
    vector<int> dist(n + 1, N + 10);
    
    queue<int> q;
    for (int v : sources){
        dist[v] = 0;
        // poss[v] = {v};
        q.push(v);
    }

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                q.push(u);
                dist[u] = dist[v] + 1;
                // poss[u] = poss[v];
            }
            // else if (dist[u] == dist[v] + 1){
            //     for (int x : poss[v])
            //         poss[u].insert(x);
            // }
        }
    }

    return dist;
}

void bfs2(int v, int d){
    dist2[v] = 0;

    queue<int> q;
    q.push(v);

    while (!q.empty()){
        int v = q.front();
        q.pop();

        mark[v] = 1;
        // cout << "Marked " << v << endl;

        if (dist2[v] == d) continue;
    
        for (int u : g[v]){
            // cout << "Checking " << u << " at distance = " << dist2[u] << endl;
            if (dist2[u] > dist2[v] + 1){
                dist2[u] = dist2[v] + 1;
                q.push(u);
                // cout << "Pusing " << u << " in the queue" << endl;
            }
        }
    }
}

void dfs(int v, int p = -1){
    par[v] = p;
    for (int u : g[v]){
        if (u == p) continue;

        h[u] = h[v] + 1;
        dfs(u, v);
    }
}

int main(){
    cin >> n >> k;

    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> vec;
    for (int i = 0; i < k; i ++)
        cin >> a[i], vec.push_back(a[i]), exist[a[i]] = 1;

    dfs(1);

    set<pair<int, int>> st;
    for (int i = 0; i < k; i ++)
        st.insert({h[a[i]], a[i]});

    vector<int> dist = bfs(vec);
    vector<int> res;
    while (!st.empty()){
        int v = (*st.rbegin()).second;
        st.erase({h[v], v});

        // cout << endl;
        // cout << "At vertex = " << v << endl;


        if (mark[v]) continue;

        int cur = v;
        while (par[cur] != -1 and dist[par[cur]] == (h[v] - h[par[cur]]))
            cur = par[cur];

        bfs2(cur, dist[cur]);

        res.push_back(cur);

        // cout << "Selected " << cur << endl;
        // cout << endl;
    }

    cout << res.size() << endl;
    for (int x : res)
        cout << x << " ";
    cout << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 67204 KB Output is correct
2 Correct 258 ms 67472 KB Output is correct
3 Correct 255 ms 67408 KB Output is correct
4 Correct 565 ms 101496 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14684 KB Output is correct
2 Correct 10 ms 14684 KB Output is correct
3 Correct 320 ms 36372 KB Output is correct
4 Correct 340 ms 38892 KB Output is correct
5 Correct 385 ms 36180 KB Output is correct
6 Correct 454 ms 38756 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14424 KB Output is correct
4 Correct 6 ms 14580 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14172 KB Output is correct
7 Correct 6 ms 14172 KB Output is correct
8 Correct 10 ms 14172 KB Output is correct
9 Incorrect 6 ms 14168 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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