Submission #544148

#	Time	Username	Problem	Language	Result	Execution time	Memory
544148		levladiator	Pastiri (COI20_pastiri)	C++14	100 / 100	626 ms	64040 KiB

pastiri

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define EPSILON 0.000001
#define CH (*s-'a')

using namespace std;

const ll NMAX = 5e5 + 5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = 1e9;

ifstream fin("sufle.in");
ofstream fout("sufle.out");

int N,K;
int sheep[NMAX],dep[NMAX],dist[NMAX],anc[NMAX],v[NMAX];
bool vis[NMAX];
vector<int> adj[NMAX],ans;

bool cmp(int a,int b)
{
    return dep[a]>dep[b];
}

void bfs()
{
    queue<int> Q;
    for(int i=1;i<=N;i++)
    {
        if(sheep[i])Q.push(i);
    }
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for(auto vec : adj[node])
        {
            if(!sheep[vec]&&!dist[vec])
            {
                dist[vec]=dist[node]+1;
                Q.push(vec);
            }
        }
    }
}

void dfs(int node,int prev,int last)
{
    dep[node]=dep[prev]+1;
    if(dist[last]+dep[last]<dist[node]+dep[node])
    {
        last=node;
    }
    anc[node]=last;
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;

        dfs(son,node,last);
    }
}

void mark(int node)
{
    vis[node]=1;
    for(auto vec : adj[node])
    {
        if(vis[vec])
            continue;

        if(dist[vec]+1==dist[node])
        {
            mark(vec);
        }
    }
}

int main()
{
    cin.tie ( 0 )->sync_with_stdio ( 0 );
    cin.tie ( NULL );
    cout.tie ( NULL );

    cin>>N>>K;
    for(int i=1;i<N;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=1;i<=K;i++)
    {
        int x;
        cin>>x;
        sheep[x]=1;
    }
    bfs();
    dfs(1,0,0);
    int cnt=0;
    for(int i=1;i<=N;i++)
    {
        if(sheep[i])
        {
            v[++cnt]=i;
        }
    }
    sort(v+1,v+K+1,cmp);
    for(int i=1;i<=K;i++)
    {
        int node=v[i];
        if(!vis[node])
        {
            ans.pb(anc[node]);
            mark(anc[node]);
        }
    }
    cout<<ans.size()<<'\n';
    for(auto x : ans)
    {
        cout<<x<<' ';
    }

    return 0;
}

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