Cod sursa(job #63316)

Utilizator alextheroTandrau Alexandru alexthero Data 27 mai 2007 19:40:21
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <stdio.h>
#include <string.h>
#include <vector>

#define pb push_back
#define nmax 30005
#define kmax 105
#define inf (int)1e8

using namespace std;

int n,k,K,x1,y1,i,d[nmax],m[nmax],tata[nmax];
char v[nmax],bag[nmax];
vector <int> e[nmax];

inline int min(int a,int b) {
	if(a > b) return b;
	else return a;
}

void dfs(int x) {
	v[x] = 1;
	int ct = 0;
	for(int i = 0; i < (int)e[x].size(); i++)
		if(!v[e[x][i]]) {
			ct++;
			break;
		}
	if(!ct) {
		d[x] = inf;
		m[x] = k;
	}
	else {
		d[x] = inf;
		m[x] = 2 * k;
		for(int i = 0; i < (int)e[x].size(); i++) 
			if(!v[e[x][i]]) {
				tata[e[x][i]] = x;
				dfs(e[x][i]);
				d[x] = min(d[x],d[e[x][i]] + 1);
			}
		for(int i = 0; i < (int)e[x].size(); i++)
			if(tata[e[x][i]] == x) 
				if(m[e[x][i]] - 1 < d[x] || m[e[x][i]] > k || d[x] >= inf) m[x] = min(m[x],m[e[x][i]] - 1);
	}
	if(m[x] == 0) {
		bag[x] = 1;
		d[x] = 0;
		m[x] = 2 * k + 1;
	}
}

int cauta(int f,int l) {
	int r = l + 1; 
	while(f <= l) {
		int mi = (f + l) / 2;
		memset(v,0,sizeof(v));
		memset(bag,0,sizeof(bag));
		k = mi;
		dfs(1);
		if(m[1] <= k) bag[1] = 1;
		int tot = 0;
		for(int i = 1; i <= n; i++) tot += bag[i];
		//printf("%d %d\n",mi,tot);
		if(tot <= K) {
			r = mi;
			l = mi - 1;
		}
		else f = mi + 1;
	}
	return r;
}

int main() {
    freopen("salvare.in","r",stdin);
	freopen("salvare.out","w",stdout);

	scanf("%d%d",&n,&K);
	for(i = 1; i < n; i++) {
		scanf("%d%d",&x1,&y1);
		e[x1].pb(y1);
		e[y1].pb(x1);
	}

	int x = cauta(0,n);

	k = x;

	memset(v,0,sizeof(v));
	memset(bag,0,sizeof(bag));
	dfs(1);
	if(m[1] <= k) bag[1] = 1;

	int tot = 0;
	for(int i = 1; i <= n; i++) tot += bag[i];

	printf("%d\n",k);
	for(int i = 1; i <= n; i++)
		if(!bag[i] && tot < K) {
			bag[i] = 1;
			tot++;
		}
	for(int i = 1; i <= n; i++)
		if(bag[i]) printf("%d ",i); printf("\n");


	return 0;
}