Submission #544230

#	Time	Username	Problem	Language	Result	Execution time	Memory
544230		robertbarbu27	Pastiri (COI20_pastiri)	C++14	100 / 100	700 ms	116776 KiB

pastiri

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
ifstream f("teroristi2.in");
ofstream g("teroristi2.out");
vector<int> adj[500005];
int N,K;
int sheep[500005],dist[500005],lvl[500005];
int best[500005];
queue<int> Q;
vector<int> v[1000005];
bool OK[500005];
vector<int> ans;
bool viz[500005];
void dfs_best(int node,int dad)
{
    lvl[node]=lvl[dad]+1;
    v[dist[node]+lvl[node]].push_back(node);
    if(OK[node]==1)
    {
        best[node]=v[dist[node]+lvl[node]].front();
    }
    for(auto x:adj[node])
    {
        if(x!=dad)
        {
            dfs_best(x,node);
        }
    }
    v[dist[node]+lvl[node]].pop_back();

}
bool cmp(int a,int b)
{
    return lvl[a]>lvl[b];
}
void removenodes(int node)
{
    viz[node]=1;
    for(auto x:adj[node])
    {
        if(dist[x]+1==dist[node]&&viz[x]==0)
        {
            removenodes(x);
        }
    }

}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) dist[i]=1e9;
    for(int i=1; i<N; i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1; i<=K; i++)
    {
        cin>>sheep[i];
        Q.push(sheep[i]);
        dist[sheep[i]]=0;
        OK[sheep[i]]=1;
    }
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for(auto x:adj[node])
        {
            if(dist[x]>dist[node]+1)
            {
                dist[x]=dist[node]+1;
                Q.push(x);
            }
        }
    }
    dfs_best(1,0);
    sort(sheep+1,sheep+K+1,cmp);
    for(int i=1; i<=K; i++)
    {
       // cout<<best[sheep[i]]<<" ";
        if(viz[sheep[i]]==0)
        {
            removenodes(best[sheep[i]]);
            ans.pb(best[sheep[i]]);
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto x:ans) cout<<x<<" ";






}

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