Submission #1212607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212607		MMihalev	Pastiri (COI20_pastiri)	C++20	100 / 100	320 ms	85472 KiB

pastiri

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX_N=5e5+4;
int n;
vector<int>g[MAX_N];
bool sheep[MAX_N];

int dist[MAX_N];
int highest[MAX_N];
int depth[MAX_N];

int dp[MAX_N][2];
int minreach[MAX_N][2];

bool place[MAX_N];
bool all[MAX_N];
vector<int>guys;
void dfs(int u,int par)
{
    for(int v:g[u])
    {
        if(v==par)continue;
        dfs(v,u);
    }

    if(sheep[u])
    {
        int both_dp=0,both_minreach=1e9;

        minreach[u][0]=1e9;minreach[u][1]=1e9;

        for(int v:g[u])
        {
            if(v==par)continue;
            both_dp+=dp[v][0];
            both_minreach=min(both_minreach,minreach[v][0]);
        }

        dp[u][1]=both_dp;minreach[u][1]=both_minreach;

        if(both_minreach>depth[u])
        {
            minreach[u][0]=depth[u];
            dp[u][0]=both_dp+1;
            place[u]=1;
        }
        else
        {
            minreach[u][0]=both_minreach;
            dp[u][0]=both_dp;
        }
    }
    else
    {
        int both_dp=0,dp_without=0,dp_with=0;

        int both_minreach=1e9,reach_without=1e9,reach_with=1e9;

        minreach[u][0]=1e9;minreach[u][1]=1e9;

        int mosthigh=highest[u];

        for(int v:g[u])
        {
            if(v==par)continue;

            if(highest[v]==mosthigh)
            {
                dp_without+=dp[v][1];
                dp_with+=dp[v][0];
                reach_with=min(reach_with,minreach[v][0]);
                reach_without=min(reach_without,minreach[v][1]);
            }
            else
            {
                both_dp+=dp[v][0];
                both_minreach=min(both_minreach,minreach[v][0]);
            }
        }

        dp[u][1]=both_dp+dp_without;
        minreach[u][1]=min(both_minreach,reach_without);

        if(both_minreach<=2*depth[u]-mosthigh)
        {
            dp[u][0]=dp[u][1];
            minreach[u][0]=minreach[u][1];
        }
        else
        {
            if(dp_with==dp_without or dist[u]+depth[u]<mosthigh)
            {
                dp[u][0]=both_dp+dp_with;
                minreach[u][0]=min(both_minreach,reach_with);
                all[u]=1;
            }
            else
            {
                dp[u][0]=both_dp+dp_without+1;
                minreach[u][0]=min(both_minreach,reach_without);
                minreach[u][0]=min(minreach[u][0],depth[u]-dist[u]);
                place[u]=1;
            }
        }
    }
}
void backdfs(int u,int par,bool state)
{
    if(state==0 && place[u])guys.push_back(u);

    if(sheep[u])
    {
        for(int v:g[u])
        {
            if(v==par)continue;

            backdfs(v,u,0);
        }
    }
    else
    {
        int mosthigh=highest[u];

        for(int v:g[u])
        {
            if(v==par)continue;

            if(highest[v]!=mosthigh)
            {
                backdfs(v,u,0);
            }
            else
            {
                if(all[u] && state==0)backdfs(v,u,0);
                else backdfs(v,u,1);
            }
        }
    }
}
void init_dfs(int u,int par)
{
    highest[u]=(sheep[u] ? depth[u] : 1e9);

    for(int v:g[u])
    {
        if(v==par)continue;

        depth[v]=depth[u]+1;

        init_dfs(v,u);

        highest[u]=min(highest[u],highest[v]);
    }
}
void bfs()
{
    queue<int>q;

    for(int i=1;i<=n;i++)
    {
        if(sheep[i])
        {
            q.push(i);
        }
        else dist[i]=-1;
    }

    while(q.size())
    {
        int u=q.front();
        q.pop();

        for(int v:g[u])
        {
            if(dist[v]!=-1)continue;

            dist[v]=dist[u]+1;

            q.push(v);
        }
    }
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int sh;
    cin>>n>>sh;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=sh;i++)
    {
        int u;
        cin>>u;
        sheep[u]=1;
    }

    init_dfs(1,0);
    bfs();

    dfs(1,0);
    backdfs(1,0,0);

    cout<<dp[1][0]<<"\n";
    for(int u:guys)cout<<u<<" ";
    cout<<"\n";

    return 0;
}

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