oj.uz

Submission #559316

# Submission time Handle Problem Language Result Execution time Memory
559316 2022-05-09T15:20:58 Z Redhood Pastiri (COI20_pastiri) C++14
100 / 100
 987 ms 139160 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
using namespace std;

typedef long long ll;
typedef long double ld;
//#define int long long
const int N = (int)5e5 + 10;
const int inf = 1e9;
vector < int > g[N];

int mnd[N];
int shrt[N], pred[N], h[N];


int ans[N][2], high[N][2];


bool done[N][2];
void dfs(int v, int p, int H){
    h[v] = H;
    pred[v] = p;
    mnd[v] = (shrt[v] == 0 ? 0 : 1e9);
    for(auto &u : g[v]){
        if(u != p){
            dfs(u , v, H + 1);
            mnd[v] = min(mnd[v] , mnd[u] + 1);
        }
    }
}
int did[N][2];
bool bst[N];
bool better(int v){
    if(ans[v][1] == ans[v][0]){
        return high[v][1] < high[v][0];
    }
    return ans[v][1] < ans[v][0];
}
void dfs1(int v){
    /// mnd[v];
    for(auto &u : g[v]){
        if(u != pred[v]){
            dfs1(u);
            if(better(u))
                bst[u] = 1;
            else
                bst[u] = 0;
        }
    }



    vector < int > small;
    for(auto &u : g[v]){
        if(u == pred[v])
            continue;
        if(mnd[u] + 1 > mnd[v]){
        }else{
            small.pb(u);
        }
    }

    for(int fl = 0;fl < 2; ++fl){
        for(auto &u : g[v]){
            if(u == pred[v])
                continue;
            if(mnd[u] + 1 > mnd[v]){
                ans[v][fl] += ans[u][1];
                high[v][fl] = min(high[v][fl], high[u][1]);
            }
        }
         if(fl == 0){
                for(auto &u : small){
                    ans[v][fl] += ans[u][bst[u]];
                    high[v][fl] = min(high[v][fl], high[u][bst[u]]);
                }
            }else{
                /// two options
                pair < int , int > now = {ans[v][fl], high[v][fl]};
                for(auto &u : small){
                    now.fi += ans[u][1];
                    now.se = min(now.se, high[u][1]);
                }
                /// another option is to cover by the current

                for(auto &u : small){
                    ans[v][1] += ans[u][bst[u]];
                    high[v][1] = min(high[v][1], high[u][bst[u]]);
                }
                int x = h[v] - high[v][fl];
                bool put = 0;
                if(x != mnd[v]){
                    if(shrt[v] == mnd[v]){
                        ans[v][fl]++, put = 1;
                        high[v][fl] = min(high[v][fl], h[v] - shrt[v]);
                    }else
                        ans[v][fl] = inf;
                }


        //        cerr << " lol " << v << ' ' << now.ans << ' ' << now.high << endl;

                if((shrt[v]==0 && (now.se != h[v]))
                || (now > mkp(ans[v][fl], high[v][fl]))){
                    did[v][fl] = 1 + put;

                }else{
                    ans[v][fl] = now.fi;
                    high[v][fl] = now.se;
                }
            }
    }




}
bool visited[N][2];
bool answ[N];
void get_ans(int v , int fl){

    if(fl == 0){
        vector < int > small;
        for(auto &u : g[v]){
            if(u == pred[v])
                continue;
            if(mnd[u] + 1 > mnd[v]){
                get_ans(u, 1);
            }else{
                get_ans(u , bst[u]);
            }
        }
    }else{
        if(did[v][fl] > 0){
            answ[v] = did[v][fl] - 1;
            for(auto &u : g[v]){
                if(u == pred[v])
                    continue;
                if(mnd[u] + 1 > mnd[v]){
                    get_ans(u, 1);
                }else{
                    get_ans(u , bst[u]);
                }
            }
        }else{
//            assert(shrt[v] != 0);
            for(auto &u : g[v]){
                if(u == pred[v])
                    continue;
                get_ans(u , 1);
            }
        }

    }
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0) , cout.tie(0);
    int n , k;
    cin >> n >> k;


    for(int i=0;i<n;++i){
        high[i][0]=high[i][1]=inf;
    }

    for(int i = 0; i < n - 1; ++i){
        int a , b;
        cin >> a >> b;
        --a, --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector < int > o(k);
    for(auto &i : o)
        cin >> i, --i;
    queue < int > bfs;
    for(auto &u : o)
        bfs.push(u);

    fill(shrt , shrt + N , -1);

    for(auto &u : o)
        shrt[u] = 0;
    while(!bfs.empty()){
        int v = bfs.front();
        bfs.pop();
        for(auto &u : g[v]){
            if(shrt[u] == -1){
                shrt[u] = shrt[v] + 1;
                bfs.push(u);
            }
        }
    }

    dfs(0 , -1, 0);




    dfs1(0);

    get_ans(0 , 1);


//    cout << "fukk \n";

//    for(int i = 0; i < n; ++i){
//        if(done[i][0])
//        cout << i << ' ' << 0 << ' ' << state[i][0].ans << '\n';
//
//        if(done[i][1])
//        cout << i << ' ' << 1 << ' ' << state[i][1].ans << '\n';
//        cout << " NEW \n";
//
//    }


    vector < int > take;
    for(int i = 0; i < n; ++i){
        if(answ[i])
            take.pb(i);
    }
    assert(sz(take) == ans[0][1]);

    cout << ans[0][1] << '\n';
    for(auto &u : take)
        cout << u + 1 << ' ';
    cout << '\n';




    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 130828 KB Output is correct
2 Correct 269 ms 132684 KB Output is correct
3 Correct 272 ms 133192 KB Output is correct
4 Correct 303 ms 139160 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 589 ms 44964 KB Output is correct
4 Correct 565 ms 47372 KB Output is correct
5 Correct 837 ms 48248 KB Output is correct
6 Correct 956 ms 55712 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14172 KB Output is correct
2 Correct 9 ms 14164 KB Output is correct
3 Correct 9 ms 14208 KB Output is correct
4 Correct 8 ms 14156 KB Output is correct
5 Correct 8 ms 14164 KB Output is correct
6 Correct 8 ms 14164 KB Output is correct
7 Correct 8 ms 14164 KB Output is correct
8 Correct 8 ms 14164 KB Output is correct
9 Correct 8 ms 14164 KB Output is correct
10 Correct 8 ms 14164 KB Output is correct
11 Correct 9 ms 14164 KB Output is correct
12 Correct 8 ms 14036 KB Output is correct
13 Correct 10 ms 14164 KB Output is correct
14 Correct 10 ms 14312 KB Output is correct
15 Correct 9 ms 14164 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 50340 KB Output is correct
2 Correct 796 ms 49896 KB Output is correct
3 Correct 719 ms 51224 KB Output is correct
4 Correct 863 ms 47968 KB Output is correct
5 Correct 568 ms 51164 KB Output is correct
6 Correct 696 ms 69268 KB Output is correct
7 Correct 768 ms 64964 KB Output is correct
8 Correct 774 ms 64472 KB Output is correct
9 Correct 987 ms 55180 KB Output is correct
10 Correct 957 ms 54816 KB Output is correct
11 Correct 643 ms 56988 KB Output is correct
12 Correct 545 ms 60628 KB Output is correct
13 Correct 638 ms 62744 KB Output is correct
14 Correct 670 ms 58148 KB Output is correct
15 Correct 105 ms 20940 KB Output is correct
16 Correct 888 ms 51956 KB Output is correct
17 Correct 613 ms 51516 KB Output is correct
18 Correct 794 ms 47604 KB Output is correct
19 Correct 912 ms 68288 KB Output is correct
20 Correct 982 ms 79436 KB Output is correct
21 Correct 812 ms 54552 KB Output is correct
22 Correct 799 ms 56632 KB Output is correct