oj.uz

Submission #382475

# Submission time Handle Problem Language Result Execution time Memory
382475 2021-03-27T12:01:26 Z VEGAnn Pastiri (COI20_pastiri) C++14
100 / 100
 927 ms 98784 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<i2> vc;
vector<int> ans, g[N], srt[N];
bool mrk[N], mrk_ans[N];
int n, k, h[N], dst[N], sh[N], up[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++)
        srt[h[sh[i]]].PB(sh[i]);

    for (int ht = n - 1; ht >= 0; ht--)
    for (int v : srt[ht]){
        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 218 ms 84588 KB Output is correct
2 Correct 227 ms 85484 KB Output is correct
3 Correct 238 ms 85484 KB Output is correct
4 Correct 407 ms 98784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24044 KB Output is correct
2 Correct 19 ms 24044 KB Output is correct
3 Correct 599 ms 45804 KB Output is correct
4 Correct 594 ms 48140 KB Output is correct
5 Correct 789 ms 46060 KB Output is correct
6 Correct 927 ms 49516 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 47596 KB Output is correct
2 Correct 786 ms 47300 KB Output is correct
3 Correct 817 ms 49480 KB Output is correct
4 Correct 806 ms 46444 KB Output is correct
5 Correct 614 ms 45156 KB Output is correct
6 Correct 748 ms 55788 KB Output is correct
7 Correct 802 ms 53376 KB Output is correct
8 Correct 825 ms 52968 KB Output is correct
9 Correct 893 ms 46584 KB Output is correct
10 Correct 768 ms 46188 KB Output is correct
11 Correct 577 ms 47872 KB Output is correct
12 Correct 586 ms 50764 KB Output is correct
13 Correct 572 ms 52960 KB Output is correct
14 Correct 488 ms 49260 KB Output is correct
15 Correct 79 ms 27884 KB Output is correct
16 Correct 852 ms 45036 KB Output is correct
17 Correct 576 ms 46048 KB Output is correct
18 Correct 761 ms 42476 KB Output is correct
19 Correct 793 ms 53780 KB Output is correct
20 Correct 839 ms 58476 KB Output is correct
21 Correct 696 ms 46572 KB Output is correct
22 Correct 699 ms 47616 KB Output is correct