oj.uz

Submission #1004091

# Submission time Handle Problem Language Result Execution time Memory
1004091 2024-06-21T05:07:08 Z vjudge1 Pastiri (COI20_pastiri) C++17
49 / 100
 819 ms 524288 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];

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 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]);

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

        for (int x : poss[cur])
            mark[x] = 1;

        res.push_back(cur);

        // cout << "Selected " << cur << 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 256 ms 113744 KB Output is correct
2 Correct 340 ms 120584 KB Output is correct
3 Correct 346 ms 120600 KB Output is correct
4 Correct 601 ms 145444 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 41820 KB Output is correct
2 Correct 9 ms 41816 KB Output is correct
3 Correct 455 ms 101088 KB Output is correct
4 Correct 483 ms 133848 KB Output is correct
5 Correct 530 ms 89196 KB Output is correct
6 Correct 554 ms 91988 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 41564 KB Output is correct
2 Correct 7 ms 41564 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 8 ms 41564 KB Output is correct
5 Correct 7 ms 41820 KB Output is correct
6 Correct 8 ms 41820 KB Output is correct
7 Correct 8 ms 41564 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 7 ms 41820 KB Output is correct
10 Correct 8 ms 41564 KB Output is correct
11 Correct 13 ms 43868 KB Output is correct
12 Correct 7 ms 41744 KB Output is correct
13 Correct 19 ms 51036 KB Output is correct
14 Correct 7 ms 41560 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 88372 KB Output is correct
2 Correct 512 ms 94980 KB Output is correct
3 Correct 780 ms 116972 KB Output is correct
4 Correct 518 ms 89392 KB Output is correct
5 Correct 655 ms 102492 KB Output is correct
6 Correct 819 ms 138172 KB Output is correct
7 Correct 776 ms 129612 KB Output is correct
8 Correct 792 ms 140512 KB Output is correct
9 Correct 555 ms 89488 KB Output is correct
10 Correct 502 ms 89428 KB Output is correct
11 Correct 480 ms 134736 KB Output is correct
12 Runtime error 751 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -