Submission #382473

#	Time	Username	Problem	Language	Result	Execution time	Memory
382473		VEGAnn	Pastiri (COI20_pastiri)	C++14	82 / 100	1002 ms	116768 KiB

pastiri

#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], nw_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 : nw_g[v]){
        if (mrk_ans[u]) 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 < n; i++)
    for (int u : g[i])
        if (dst[i] - 1 == dst[u])
            nw_g[i].PB(u);

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

        assert(!mrk_ans[who]);

        ans.PB(who);

        dfsik(who);
    }

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

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

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51