oj.uz

Submission #1004095

# Submission time Handle Problem Language Result Execution time Memory
1004095 2024-06-21T05:16:04 Z vjudge1 Pastiri (COI20_pastiri) C++17
41 / 100
 1000 ms 98860 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> 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){
    vector<int> dist(n + 1, N + 10);
    dist[v] = 0;

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

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

        if (dist[v] == d and exist[v])
            mark[v] = 1;

        if (dist[v] >= d) continue;
    
        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

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 << "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 << res.size() << endl;
    for (int x : res)
        cout << x << " ";
    cout << endl;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 67668 KB Output is correct
2 Correct 322 ms 67860 KB Output is correct
3 Correct 321 ms 67756 KB Output is correct
4 Execution timed out 1067 ms 98860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 342 ms 43752 KB Output is correct
4 Correct 356 ms 50204 KB Output is correct
5 Correct 370 ms 38324 KB Output is correct
6 Correct 570 ms 39248 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 6 ms 16984 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16912 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 10 ms 17048 KB Output is correct
14 Correct 4 ms 16984 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 40596 KB Time limit exceeded
2 Halted 0 ms 0 KB -