Submission #986323

#	Time	Username	Problem	Language	Result	Execution time	Memory
986323		alexdd	Pastiri (COI20_pastiri)	C++17	31 / 100	1035 ms	108916 KiB

pastiri

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
int n,k;
vector<int> con[500005];
int closest[500005];
int mind[500005];
int depth[500005];
int cnt[500005];
bool isoaie[500005];
vector<int> sol;
int init;
void dfs_sterge(int nod, int par, int d)
{
    if(d==0)
    {
        isoaie[nod]=0;
        return;
    }
    for(auto adj:con[nod])
        if(adj!=par)
            dfs_sterge(adj,nod,d-1);
}
void sterge(int nod, int d)
{
    init=nod;
    dfs_sterge(nod,0,d);
}
void dfs(int nod, int par)
{
    mind[nod]=INF;
    if(closest[nod]==0) mind[nod]=depth[nod];
    for(auto adj:con[nod])
    {
        if(adj==par)
            continue;
        depth[adj]=depth[nod]+1;
        dfs(adj,nod);
        mind[nod] = min(mind[nod], mind[adj]);
    }
}
bool cmp(int x, int y)
{
    return mind[x] > mind[y];
}
void dfs2(int nod, int par)
{
    cnt[nod]=0;
    sort(con[nod].begin(),con[nod].end(),cmp);
    for(auto adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs2(adj,nod);
        if(cnt[adj]==0)
            continue;
        if(mind[adj]!=mind[nod] || mind[nod]-depth[nod] > closest[nod])
        {
            sol.push_back(adj);
            sterge(adj,closest[adj]);
            cnt[adj]=0;
        }
        else
            cnt[nod] += cnt[adj];
    }
    if(isoaie[nod]) cnt[nod]++;
    if(cnt[nod]==0)
        return;
    if(mind[nod]-depth[nod]==closest[nod] && (nod==1 || mind[nod]-depth[par]!=closest[par]))
    {
        sol.push_back(nod);
        sterge(nod,closest[nod]);
        cnt[nod]=0;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        closest[i]=INF;
    deque<int> dq;
    for(int i=1;i<=k;i++)
    {
        cin>>u;
        isoaie[u]=1;
        closest[u]=0;
        dq.push_back(u);
    }
    while(!dq.empty())
    {
        int nod = dq.front();
        dq.pop_front();
        for(auto adj:con[nod])
        {
            if(closest[adj] > closest[nod]+1)
            {
                closest[adj] = closest[nod]+1;
                dq.push_back(adj);
            }
        }
    }
    depth[1]=1;
    dfs(1,0);
    dfs2(1,0);
    cout<<sol.size()<<"\n";
    for(auto x:sol)
        cout<<x<<" ";
    return 0;
}

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