Submission #485541

#	Time	Username	Problem	Language	Result	Execution time	Memory
485541		blue	Pastiri (COI20_pastiri)	C++17	23 / 100	1122 ms	463084 KiB

pastiri

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

const int maxN = 500'000;
const int INF = 1'000'000'000;
const int logN = 20;

int N, K;
vector<int> edge[1+maxN];
vector<int> sheep_dist(1+maxN, INF);
vector<int> depth(1+maxN, 0);

vector<int> st;

vector<int> limit(1+maxN);

int anc[1+maxN][1+logN];
vector<int> parent(1+maxN);

vector<int> subtree(1+maxN, 1);

void dfs(int u, int p)
{
    anc[u][0] = p;
    st.push_back(u);

    for(int v: edge[u])
    {
        if(v == p) continue;
        depth[v] = 1 + depth[u];
        dfs(v, u);
        subtree[u] += subtree[v];
    }

    if(sheep_dist[u] == 0)
    {
        int lo = 0;
        int hi = int(st.size()) - 1;
        while(lo != hi)
        {
            int mid = (lo+hi)/2;
            if(sheep_dist[ st[mid] ] < depth[u] - depth[ st[mid] ])
                lo = mid+1;
            else
                hi = mid;
        }

        limit[u] = st[lo];
        // cerr << "shepherd of " << u << " = " << st[lo] << '\n';
    }


    st.pop_back();
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);

    for(int e = logN; e >= 0; e--)
    {
        if(depth[v] - (1 << e) >= depth[u])
            v = anc[v][e];
    }

    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] != anc[v][e])
        {
            u = anc[u][e];
            v = anc[v][e];
        }
    }

    return anc[u][0];
}

int dist(int u, int v)
{
    return depth[u] + depth[v] - 2*depth[lca(u,v)];
}






















vector<bool> blocked(1+maxN, 0);

vector<int> centroid_parent(1+maxN, 0);
vector<int> parent_dist(1+maxN);
vector< deque< pair<int, int> > > reach_list(1+maxN);



int get_size(int u, int v) // u -> v =
{
    if(parent[u] == v)
        return N - subtree[u];
    else
        return subtree[v];
}

vector<bool> reach_visit(1+maxN, 0);
queue<int> tbv;
queue<int> tbvd;


vector<int> last_visit(1+maxN, 0);


void build_centroid(int u)
{
    while(1)
    {
        int next_pos = -1;
        for(int v: edge[u])
        {
            if(blocked[v]) continue;
            if(2*get_size(u, v) > N)
            {
                next_pos = v;
                break;
            }
        }

        if(next_pos == -1) break;
        u = next_pos;
    }





    while(!tbv.empty()) tbv.pop();

    last_visit[u] = u;
    tbv.push(u);
    tbvd.push(0);
    while(!tbv.empty())
    {
        int s = tbv.front();
        tbv.pop();

        int d = tbvd.front();
        tbvd.pop();

        if(sheep_dist[s] == 0)
            reach_list[u].push_back(make_pair(d, s));

        for(int t: edge[s])
        {
            if(blocked[t]) continue;
            if(last_visit[t] == u) continue;

            last_visit[t] = u;
            tbv.push(t);
            tbvd.push(d+1);
        }
    }


    blocked[u] = 1;
    for(int v: edge[u])
    {
        if(blocked[v]) continue;
        centroid_parent[v] = u;
        build_centroid(v);
    }





}

vector<int> covered(1+maxN, 0);


void cover_sheep(int u)
{
    int d = sheep_dist[u];

    int adj = 0;

    for(int v = u; v != 0; v = centroid_parent[v])
    {
        while(1)
        {
            if(reach_list[v].empty()) break;

            if(covered[reach_list[v][0].second])
            {
                reach_list[v].pop_front();
                continue;
            }

            if(reach_list[v][0].first + adj > d) break;

            covered[reach_list[v][0].second] = 1;
            reach_list[v].pop_front();
        }

        adj += parent_dist[v];
    }
}





















int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    for(int i = 1; i <= N-1; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    queue<int> tbv;
    for(int k = 1; k <= K; k++)
    {
        int o;
        cin >> o;
        tbv.push(o);
        sheep_dist[o] = 0;
    }

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        for(int v: edge[u])
        {
            if(sheep_dist[v] <= 1 + sheep_dist[u]) continue;
            sheep_dist[v] = 1 + sheep_dist[u];
            tbv.push(v);
        }
    }

    anc[0][0] = 0;
    dfs(1, 0);
    for(int e = 1; e <= 20; e++)
        for(int u = 0; u <= N; u++)
            anc[u][e] = anc[ anc[u][e-1] ][e-1];






    for(int i = 1; i <= N; i++) parent[i] = anc[i][0];








    build_centroid(1);



    // cerr << "C = " << '\n';
    // for(int i = 1; i <= N; i++) cerr << i << ' ' << centroid_parent[i] << "\n";
    for(int i = 1; i <= N; i++)
    {
        if(centroid_parent[i] == 0) parent_dist[i] = 0;
        else parent_dist[i] = dist(i, centroid_parent[i]);
    }


    // cerr << "reach list: ";
    // for(int i = 1; i <= N; i++)
    // {
    //     cerr << i << ": ";
    //     for(auto fg: reach_list[i]) cerr << fg.second << "/" << fg.first << " ";
    //     cerr << "\n";
    // }
    // cerr << '\n';












    vector<int> sheep_pos;
    for(int i = 1; i <= N; i++)
        if(sheep_dist[i] == 0)
            sheep_pos.push_back(i);

    sort(sheep_pos.begin(), sheep_pos.end(), [] (int f, int g)
    {
        return depth[f] > depth[g];
    });

    vector<int> res;

    // assert(int(sheep_pos.size()) <= 15);

    for(int s: sheep_pos)
    {
        if(covered[s]) continue;

        int t = limit[s];

        res.push_back(t);

        cover_sheep(t);

        // for(int i: sheep_pos)
        // {
        //     if(covered[i]) continue;
        //
        //     if(dist(t, i) == depth[s] - depth[t])
        //         covered[i] = 1;
        // }

    }

    cout << (int)res.size() << '\n';
    for(int r: res) cout << r << ' ';
    cout << "\n";
}

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