oj.uz

Submission #382483

# Submission time Handle Problem Language Result Execution time Memory
382483 2021-03-27T12:37:12 Z VEGAnn Pastiri (COI20_pastiri) C++14
100 / 100
 922 ms 80864 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);

    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 calc_up(int v, int p){
    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;

        calc_up(u, v);
    }
}

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

    calc_up(0, -1);

    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 216 ms 74860 KB Output is correct
2 Correct 218 ms 75648 KB Output is correct
3 Correct 215 ms 75756 KB Output is correct
4 Correct 315 ms 80864 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 13 ms 12396 KB Output is correct
3 Correct 632 ms 35948 KB Output is correct
4 Correct 579 ms 38472 KB Output is correct
5 Correct 754 ms 36332 KB Output is correct
6 Correct 922 ms 39916 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12268 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 12 ms 12284 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 9 ms 12268 KB Output is correct
12 Correct 10 ms 12140 KB Output is correct
13 Correct 10 ms 12268 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 793 ms 37612 KB Output is correct
2 Correct 767 ms 37612 KB Output is correct
3 Correct 789 ms 39656 KB Output is correct
4 Correct 836 ms 36716 KB Output is correct
5 Correct 624 ms 34920 KB Output is correct
6 Correct 778 ms 44652 KB Output is correct
7 Correct 792 ms 42784 KB Output is correct
8 Correct 822 ms 42340 KB Output is correct
9 Correct 882 ms 36716 KB Output is correct
10 Correct 751 ms 36460 KB Output is correct
11 Correct 601 ms 37996 KB Output is correct
12 Correct 574 ms 40940 KB Output is correct
13 Correct 576 ms 42348 KB Output is correct
14 Correct 477 ms 39404 KB Output is correct
15 Correct 86 ms 16364 KB Output is correct
16 Correct 836 ms 34964 KB Output is correct
17 Correct 573 ms 35808 KB Output is correct
18 Correct 780 ms 32236 KB Output is correct
19 Correct 819 ms 43244 KB Output is correct
20 Correct 802 ms 48108 KB Output is correct
21 Correct 696 ms 36972 KB Output is correct
22 Correct 699 ms 37612 KB Output is correct