oj.uz

Submission #382486

# Submission time Handle Problem Language Result Execution time Memory
382486 2021-03-27T12:39:16 Z VEGAnn Pastiri (COI20_pastiri) C++14
100 / 100
 785 ms 80736 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
vector<int> ans, g[N];
bool mrk[N], mrk_ans[N];
int n, k, h[N], dst[N], sh[N], up[N];
int cnt[N], srt[N];

void dfs(int v, int p){
    dst[v] = oo;

    if (mrk[v])
        dst[v] = 0;

    for (int u : g[v]){
        if (u == p) continue;

        h[u] = h[v] + 1;

        dfs(u, v);

        dst[v] = min(dst[v], dst[u] + 1);
    }
}

void calc_dst(int v, int p, int mn_up){
    int mn1 = oo, mn2 = oo;

    for (int u : g[v]){
        if (u == p) continue;

        if (dst[u] + 1 < mn1){
            mn2 = mn1;
            mn1 = dst[u] + 1;
        } else if (dst[u] + 1 < mn2)
            mn2 = dst[u] + 1;
    }

    if (mrk[v])
        mn_up = 0;

    dst[v] = min(dst[v], mn_up);

    if (v == 0)
        up[v] = 0;
    else {
        if (dst[v] == dst[p] - 1)
            up[v] = up[p];
        else up[v] = v;
    }

    for (int u : g[v]){
        if (u == p) continue;

        int nw = oo;

        if (dst[u] + 1 == mn1)
            nw = min(mn_up, mn2);
        else nw = min(mn_up, mn1);

        calc_dst(u, v, nw + 1);
    }
}

void dfsik(int v){
    mrk_ans[v] = 1;

    for (int u : g[v]){
        if (mrk_ans[u] || dst[v] != dst[u] + 1) continue;

        dfsik(u);
    }
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;

        x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

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

        sh[i] = x;

        mrk[x] = 1;
    }

    h[0] = 0;

    dfs(0, -1);
    calc_dst(0, -1, oo);

    for (int i = 0; i < k; i++)
        cnt[h[sh[i]]]++;

    for (int i = 0, mem = 0; i < n; i++){
        int cur = mem + cnt[i];

        cnt[i] = mem;

        mem = cur;
    }

    for (int i = 0; i < k; i++){
        int loc = cnt[h[sh[i]]]++;

        srt[loc] = sh[i];
    }

    reverse(srt, srt + k);

    for (int i = 0; i < k; i++) {
        int v = srt[i];

        if (mrk_ans[v]) continue;

        int who = up[v];

        ans.PB(who);

        dfsik(who);
    }

    cout << sz(ans) << '\n';

    for (int cr : ans)
        cout << cr + 1 << " ";

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 74860 KB Output is correct
2 Correct 202 ms 75884 KB Output is correct
3 Correct 212 ms 75756 KB Output is correct
4 Correct 314 ms 80736 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12396 KB Output is correct
2 Correct 14 ms 12396 KB Output is correct
3 Correct 568 ms 35948 KB Output is correct
4 Correct 530 ms 38580 KB Output is correct
5 Correct 645 ms 36332 KB Output is correct
6 Correct 785 ms 39660 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 37716 KB Output is correct
2 Correct 671 ms 37612 KB Output is correct
3 Correct 755 ms 39656 KB Output is correct
4 Correct 683 ms 36588 KB Output is correct
5 Correct 544 ms 34976 KB Output is correct
6 Correct 728 ms 44744 KB Output is correct
7 Correct 726 ms 42748 KB Output is correct
8 Correct 735 ms 42428 KB Output is correct
9 Correct 766 ms 37148 KB Output is correct
10 Correct 632 ms 36588 KB Output is correct
11 Correct 561 ms 38124 KB Output is correct
12 Correct 560 ms 40812 KB Output is correct
13 Correct 568 ms 42348 KB Output is correct
14 Correct 469 ms 39404 KB Output is correct
15 Correct 88 ms 16364 KB Output is correct
16 Correct 736 ms 35052 KB Output is correct
17 Correct 543 ms 35680 KB Output is correct
18 Correct 663 ms 32368 KB Output is correct
19 Correct 713 ms 43244 KB Output is correct
20 Correct 681 ms 47984 KB Output is correct
21 Correct 603 ms 36844 KB Output is correct
22 Correct 629 ms 37532 KB Output is correct