Cod sursa(job #1566744)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 12 ianuarie 2016 15:50:26
Problema Salvare Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define Nmax 1005
#define INF 1000000000
#define pb push_back

using namespace std;

int n,k,x,cnt,dist[Nmax],minn[Nmax];
vector <int> L[Nmax],aux,ans;

inline void Dfs(int nod, int tata)
{
    int Node;
    for(auto it : L[nod])
    {
        if(it==tata) continue;
        Dfs(it,nod);
        if(dist[it]+1 > dist[nod])
        {
            dist[nod]=dist[it]+1; Node=it;
        }
        minn[nod]=min(minn[nod],minn[it]+1);
    }
    if(dist[nod]==x)
    {
        ++cnt; dist[nod]=-x-1;
        aux.pb(nod);
        return;
    }
    int maxx=-INF;
    for(auto it : L[nod])
    {
        if(it==tata || it==Node) continue;
        maxx=max(maxx,x-(minn[it]+2+x));
    }
    if(nod==1 && maxx < 1+dist[1])
    {
        ++cnt; aux.pb(1);
    }
}

inline bool Ok(int d)
{
    x=d; cnt=0;
    for(int i=1;i<=n;++i)
    {
        dist[i]=0; minn[i]=INF;
    }
    aux.clear();
    Dfs(1,0);
    return (cnt<=k);
}

int main()
{
    int i,x,y;
    ifstream cin("salvare.in");
    ofstream cout("salvare.out");
    cin>>n>>k;
    for(i=1;i<n;++i)
    {
        cin>>x>>y;
        L[x].pb(y); L[y].pb(x);
    }
    int st=0,dr=n,mij,sol;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        if(Ok(mij))
        {
            sol=mij;
            ans.clear();
            for(auto it : aux) ans.pb(it);
            dr=mij-1;
        }
        else st=mij+1;
    }
    cout<<sol<<"\n";
    sort(ans.begin(),ans.end());
    for(auto it : ans) cout<<it<<" ";
    cout<<"\n";
}