Submission #986340

#	Time	Username	Problem	Language	Result	Execution time	Memory
986340		alexdd	Pastiri (COI20_pastiri)	C++17	100 / 100	611 ms	164744 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];
bool isoaie[500005];
vector<int> sol;
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 x, int d)
{
    dfs_sterge(x,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];
}
set<int> s[500005];
bool gata[500005];
void dfs2(int nod, int par)
{
    sort(con[nod].begin(),con[nod].end(),cmp);
    bool rau=0;
    for(auto adj:con[nod])
    {
        if(adj==par || mind[adj]==INF)
            continue;

        dfs2(adj,nod);
        if(s[nod].find(2*depth[nod]-mind[nod])!=s[nod].end())
            gata[adj]=1;

        if((int)s[adj].size() > (int)s[nod].size())
            swap(s[adj],s[nod]);
        for(auto x:s[adj])
            s[nod].insert(x);

        if(gata[adj])
            continue;

        if(mind[adj]!=mind[nod] || mind[nod]-depth[nod] > closest[nod])
        {
            sol.push_back(adj);
            ///sterge(adj,closest[adj]);
            s[nod].insert(depth[adj]-closest[adj]);
            gata[adj]=1;
        }
        else
            rau=1;
    }
    if(mind[nod]==INF)
    {
        gata[nod]=1;
        return;
    }
    if(closest[nod]==0 && s[nod].find(2*depth[nod]-mind[nod])!=s[nod].end())
    {
        gata[nod]=1;
        return;
    }
    if(mind[nod]-depth[nod] > closest[nod])
    {
        gata[nod]=1;
        return;
    }
    if(closest[nod]==0)
        rau=1;
    if(!rau)
    {
        gata[nod]=1;
        return;
    }
    if(mind[nod]-depth[nod]==closest[nod] && (nod==1 || mind[nod]-depth[par]!=closest[par]))
    {
        //cout<<nod<<" sters nod\n";
        sol.push_back(nod);
        ///sterge(nod,closest[nod]);
        s[nod].insert(depth[nod]-closest[nod]);
        gata[nod]=1;
    }
}
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;
}
/**

depth[x] - closest[x] = 2*depth[nod] - mind[nod]

*/

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