Cod sursa(job #164970)

Utilizator maguaAndrei Dragus magua Data 25 martie 2008 00:04:58
Problema Salvare Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
#define vii vector<int> ::iterator

const int maxn = 100001;
const int inf = -1000000000;

vector<int> tree[maxn];
int viz[maxn];
int cost[maxn];
int acoperit[maxn];
int n,m,d,nr;

void dfs(int i)
{
viz[i]=1;

if(tree[i].size()==1 && i!=1) 
                    {
                    cost[i]=0;
                    acoperit[i]=-1;
                    return;
                    }
for(vii it=tree[i].begin();it!=tree[i].end();it++)
        if(!viz[*it])
                     {
                       acoperit[*it]=acoperit[i]-1;
                       dfs(*it);
                       cost[i]=max(cost[i],cost[*it]+1);
                       acoperit[i]=max(acoperit[i],acoperit[*it]-1);                           
                     }
if(cost[i]<=acoperit[i])cost[i]=-acoperit[i]-1;//era 0 inainte
if(cost[i]==d)
              {
               nr++;
               cost[i]=-d-1;
               acoperit[i]=d;      
              }
//fprintf(stderr,"%d : %d : %d\n",i,cost[i],acoperit[i]);
}




int main()
{
FILE *in,*out;
int i,j,k,l,temp,temp2,a,b;

in=fopen("salvare.in","r");
out=fopen("salvare.out","w");


fscanf(in,"%d",&n);
fscanf(in,"%d",&m);

for(i=1;i<n;i++)
        {
        fscanf(in,"%d %d",&a,&b);
         tree[a].push_back(b); 
         tree[b].push_back(a);      
                           
        }
fclose(in);





a=1;
b=n;
while(! (a==b && a==d ))
{
           d=(a+b)/2;
           nr=0;
           for(i=1;i<=n;i++) 
                  {
                  viz[i]=0;
                  cost[i]=inf;
                  acoperit[i]=-1;
                  }
           dfs(1);
           if(cost[1]>=0 && acoperit[1]<cost[1])
              {
              nr++;
              cost[1]=-d-1;
              }

         //  fprintf(stderr,"a=%d b=%d d=%d nr=%d m=%d\n",a,b,d,nr,m);
          // for(i=1;i<=n;i++)
         //        if(cost[i]==(-d-1))fprintf(stderr,"%d ",i);
         //  fprintf(stderr,"\n");
                 
           if(nr<=m)b=d;
           else a=d+1;

}

     

fprintf(out,"%d \n",d);
for(i=1;i<=n;i++)
                 if(cost[i]==(-d-1))fprintf(out,"%d ",i);



fclose(out);
return 0;    
}