Cod sursa(job #1486031)

Utilizator enedumitruene dumitru enedumitru Data 13 septembrie 2015 17:05:50
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#define Nmax 1024
#define mp make_pair
using namespace std;
ifstream f("salvare.in"); ofstream g("salvare.out");
int N,K,nv,a[Nmax][Nmax],deg[Nmax],up[Nmax];
pair <int, int> V[Nmax];
char U[Nmax],sol[Nmax];
void DFS(int n, int lev)
{   V[nv++]=mp(lev,n);
    for(int *p=a[n];*p;p++)
        if(*p!=up[n]) {up[*p]=n; DFS(*p,lev-1);}
}
void DFS2(int n, int up, int d)
{   U[n]=1;
    if(d==0) return;
    for(int *p=a[n];*p;p++)
        if(*p!=up) DFS2(*p,n,d-1);
}
int works(int D)
{   memset(U,0,sizeof(U));
    memset(sol,0,sizeof(sol));
    int ret=0;
    for(int i=0;i<nv;i++)
    {   int j=V[i].second;
        if(U[j]) continue;
        for(int d=D;up[j] && d;j=up[j],d--);
        sol[j]=1; ret++;
        DFS2(j,0,D);
    }
    return ret;
}
int main()
{   int i,j,r;
    f>>N>>K;
    for(r=1;r<N;r++)
        {f>>i>>j; a[i][deg[i]++]=j; a[j][deg[j]++]=i;}
    DFS(1,0);
    sort(V,V+nv);
    for(r=1;r<N;r<<=1);
    for(i=N;r;r>>=1)
        if(i-r>=0 && works(i-r)<= K) i-=r;
    K-=works(i);
    for(j=1;j<=N && K;j++)
        if(!sol[j]){sol[j]=1; K--;}
    g<<i<<'\n';
    for(j=1;j<=N;j++) if(sol[j]) g<<j<<' ';
    g<<'\n'; g.close(); return 0;
}