oj.uz

Submission #382471

# Submission time Handle Problem Language Result Execution time Memory
382471 2021-03-27T11:56:51 Z VEGAnn Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 116704 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], 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];

        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 260 ms 112236 KB Output is correct
2 Correct 287 ms 112856 KB Output is correct
3 Correct 267 ms 112876 KB Output is correct
4 Correct 429 ms 116704 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35948 KB Output is correct
2 Correct 27 ms 35948 KB Output is correct
3 Correct 752 ms 73208 KB Output is correct
4 Correct 703 ms 75116 KB Output is correct
5 Correct 867 ms 73452 KB Output is correct
6 Execution timed out 1036 ms 77064 KB Time limit exceeded

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35820 KB Output is correct
2 Correct 26 ms 35820 KB Output is correct
3 Correct 29 ms 35692 KB Output is correct
4 Correct 26 ms 35820 KB Output is correct
5 Correct 24 ms 35820 KB Output is correct
6 Correct 24 ms 35692 KB Output is correct
7 Correct 25 ms 35820 KB Output is correct
8 Correct 24 ms 35820 KB Output is correct
9 Correct 24 ms 35820 KB Output is correct
10 Correct 24 ms 35820 KB Output is correct
11 Correct 23 ms 35692 KB Output is correct
12 Correct 24 ms 35692 KB Output is correct
13 Correct 24 ms 35692 KB Output is correct
14 Correct 24 ms 35820 KB Output is correct
15 Correct 24 ms 35820 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 74768 KB Output is correct
2 Correct 915 ms 74408 KB Output is correct
3 Correct 905 ms 70724 KB Output is correct
4 Correct 966 ms 73804 KB Output is correct
5 Correct 675 ms 63604 KB Output is correct
6 Correct 869 ms 74704 KB Output is correct
7 Correct 882 ms 74116 KB Output is correct
8 Correct 908 ms 74596 KB Output is correct
9 Execution timed out 1018 ms 74000 KB Time limit exceeded
10 Halted 0 ms 0 KB -