Cod sursa(job #1597225)

Utilizator gabib97Gabriel Boroghina gabib97 Data 11 februarie 2016 20:09:08
Problema Salvare Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf 10000000
using namespace std;
int n,k,i,x,y,l[1001],t[1001],v[1001],sol[1001],r;
bool o[1001];
vector<int> G[1001];
bool comp(int a,int b)
{
    return l[a]>l[b];
}
void DFS(int s,int nivel)
{
    int i,z=G[s].size();
    o[s]=1; l[s]=nivel;
    for (i=0;i<z;i++)
        if (!o[G[s][i]])
        {
            DFS(G[s][i],nivel+1);
            t[G[s][i]]=s;
        }
}
void fill(int s,int h)
{
    int i,z=G[s].size();
    o[s]=1;
    for (i=0;i<z;i++)
        if (!o[G[s][i]]&&h)
            fill(G[s][i],h-1);
}
int det(int h)
{
    int i,nr=0,j;
    for (i=1;i<=n;i++) o[i]=0;
    for (i=1;i<=n;i++)
        if (!o[v[i]])
    {
        int aux=h;
        nr++;
        for (j=v[i];t[j]&&aux;j=t[j]) aux--;
        sol[nr]=j;
        fill(j,h);
    }
    r=nr;
    return nr;
}
int cautare(int a,int b)
{
    int m=(a+b)>>1;
    if (a==b) return a;
    if (det(m)<=k) return cautare(a,m);
    else return cautare(m+1,b);
}
int main()
{
    freopen ("salvare.in","r",stdin);
    freopen ("salvare.out","w",stdout);
    scanf("%i%i",&n,&k);
    for (i=1;i<n;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
        v[i]=i;

    }
    v[n]=n;
    DFS(1,0);
    sort(v+1,v+n+1,comp);
    int y=cautare(0,n);
    det(y);
    printf("%i\n",y);
    sort(sol+1,sol+r+1);
    for (i=1;i<=r;i++)
        printf("%i ",sol[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}