Cod sursa(job #2789230)

Utilizator marcumihaiMarcu Mihai marcumihai Data 27 octombrie 2021 10:43:17
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("salvare.in");
ofstream g ("salvare.out");


int n,k;
int dp[10005];
vector <int> v[10005];
int rez;
void dfs(int nod, int tata, int dist )
{

    int maxim=0;
    int vecini=0;
    for(int x=0; x<v[nod].size(); ++x)
    {
        if(v[nod][x]!=tata)
        {
            int fiu=v[nod][x];
            dfs(fiu,nod,dist);
            maxim=min(maxim , dp[fiu]);
             ++vecini;
        }

    }
    if(maxim>=dist)
    {
        ++rez;
        dp[nod]=0;
    }
    else
    {
        dp[nod]=maxim+1;
    }
}

int ok(int dist)
{
    rez=0;
    for(int i=1; i<=n; ++i)
        dp[i]=0;

    dfs(1, 0, dist);


    if(rez>k)
        return 0;
    return 1;

}
int main()
{
    f>>n>>k;
    for(int i=1; i<=n; ++i)
    {
        int x, y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int st=1;
    int dr=n;

    int mij=(st+dr)/2;
    while(st<=dr)
    {
        int lejereanu=ok(mij);
        if(lejereanu==1 && ok(mij-1)==0)
        {
            g<<mij<<"\n";
            break;
        }
        if(ok(mij)==0)
            st=mij+1;
        else
            dr=mij-1;

        mij=(st+dr)/2;
    }


    ok(mij);

    int sol[10005];
    int nr=0;



    for(int i=1; i<=n; ++i)
        if(dp[i]==0)
            sol[++nr]=i;

    for(int i=1;i<=n;++i)
    {
        if(nr<k && dp[i]!=0)
            sol[++nr]=i;
    }
    sort(sol+1 , sol+k+1);
    for(int i=1;i<=k;++i)
        g<<sol[i]<<" ";
    return 0;
}