Submission #559223

#	Time	Username	Problem	Language	Result	Execution time	Memory
559223		Redhood	Pastiri (COI20_pastiri)	C++14	31 / 100	1079 ms	133348 KiB

pastiri

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

const int N = (int)5e5 + 10;
const int inf = 1e9;
vector < int > g[N];

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

struct kek{
    int ans;
    int high;
    kek(){
        ans = 0;
        high = 1e9;
    }
};

kek state[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 better(kek a , kek b){
    if(a.ans == b.ans){
        return a.high < b.high;
    }
    return a.ans < b.ans;
}
void dfs1(int v, int fl){
    /// mnd[v];
    if(done[v][fl])
        return;
    done[v][fl] = 1;
    vector < int > small;
    for(auto &u : g[v]){
        if(u == pred[v])
            continue;
        if(mnd[u] + 1 > mnd[v]){
            dfs1(u, 1);
            state[v][fl].ans += state[u][1].ans;
            state[v][fl].high = min(state[v][fl].high, state[u][1].high);
        }else{
            small.pb(u);
        }
    }

    if(fl == 0){
        for(auto &u : small){
            bool t = 0;

            dfs1(u , 1);
            dfs1(u , 0);

            if(better(state[u][1], state[u][0]))
                t = 1;
            else
                t = 0;

            state[v][fl].ans += state[u][t].ans;
            state[v][fl].high = min(state[v][fl].high, state[u][t].high);
        }
    }else{
        /// two options
        kek now = state[v][fl];
        for(auto &u : small){
            dfs1(u , 1);
            dfs1(u , 0);
            now.ans += state[u][1].ans;
            now.high = min(state[v][fl].high, state[u][1].high);
        }
        /// another option is to cover by the current

        for(auto &u : small){
            bool t=0;
            if(better(state[u][1], state[u][0]))
                t = 1;
            else
                t = 0;
            state[v][1].ans += state[u][t].ans;
            state[v][1].high = min(state[v][1].high, state[u][t].high);
        }
        int x = h[v] - state[v][fl].high;

        bool put = 0;
        if(x != mnd[v]){
            if(shrt[v] == mnd[v]){
                state[v][fl].ans++, put = 1;
                state[v][fl].high = min(state[v][fl].high, h[v] - shrt[v]);
            }else
                state[v][fl].ans = inf;
        }


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

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

        }else{
            state[v][fl] = now;
        }
    }
}
bool visited[N][2];
bool ans[N];
void get_ans(int v , int fl){
    assert(!visited[v][fl]);
    visited[v][fl] = 1;

    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{
                bool t = 0;
                if(better(state[u][1], state[u][0]))
                    t = 1;
                else
                    t = 0;
                get_ans(u , t);
            }
        }
    }else{
        if(did[v][fl] > 0){
            ans[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{
                    bool t = 0;
                    if(better(state[u][1], state[u][0]))
                        t = 1;
                    else
                        t = 0;
                    get_ans(u , t);
                }
            }
        }else{
            for(auto &u : g[v]){
                if(u == pred[v])
                    continue;
                get_ans(u , 1);
            }
        }

    }
}
signed main(){
    int n , k;
    cin >> n >> k;
    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 , 1);

    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(ans[i])
            take.pb(i);
    }
    assert(sz(take) == state[0][1].ans);

    cout << state[0][1].ans << endl;
    for(auto &u : take)
        cout << u + 1 << ' ';
    cout << endl;
    return 0;
}

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