oj.uz

Submission #382469

# Submission time Handle Problem Language Result Execution time Memory
382469 2021-03-27T11:53:20 Z VEGAnn Pastiri (COI20_pastiri) C++14
82 / 100
 1000 ms 107828 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];
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++)
        vc.PB({h[sh[i]], sh[i]});

    sort(all(vc));
    reverse(all(vc));

    for (i2 cr : vc){
        int v = cr[1];

        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 258 ms 106860 KB Output is correct
2 Correct 262 ms 107828 KB Output is correct
3 Correct 261 ms 101228 KB Output is correct
4 Correct 359 ms 99028 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24300 KB Output is correct
2 Correct 20 ms 24300 KB Output is correct
3 Correct 713 ms 63724 KB Output is correct
4 Correct 701 ms 63468 KB Output is correct
5 Correct 878 ms 61804 KB Output is correct
6 Execution timed out 1018 ms 65320 KB Time limit exceeded

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 69612 KB Output is correct
2 Correct 885 ms 69960 KB Output is correct
3 Correct 944 ms 67924 KB Output is correct
4 Correct 949 ms 68904 KB Output is correct
5 Correct 724 ms 59480 KB Output is correct
6 Correct 877 ms 72540 KB Output is correct
7 Correct 956 ms 70884 KB Output is correct
8 Correct 978 ms 71108 KB Output is correct
9 Correct 988 ms 68716 KB Output is correct
10 Correct 878 ms 68332 KB Output is correct
11 Correct 743 ms 69996 KB Output is correct
12 Correct 696 ms 69984 KB Output is correct
13 Correct 651 ms 71012 KB Output is correct
14 Correct 643 ms 71404 KB Output is correct
15 Correct 97 ms 31088 KB Output is correct
16 Correct 960 ms 65000 KB Output is correct
17 Correct 650 ms 59868 KB Output is correct
18 Correct 827 ms 60524 KB Output is correct
19 Correct 934 ms 73744 KB Output is correct
20 Correct 956 ms 79080 KB Output is correct
21 Correct 867 ms 68948 KB Output is correct
22 Correct 822 ms 69740 KB Output is correct