Cod sursa(job #92469)

Utilizator filipbFilip Cristian Buruiana filipb Data 15 octombrie 2007 18:13:18
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define minim(a, b) ((a < b) ? a : b)
#define pb push_back
#define INF 2000000001
#define NMax 1005

int N, K, q[NMax], uz[NMax], t[NMax], dist[NMax], up[NMax], bst;
vector<int> G[NMax];

void compute(int X, int n)
{
    int i, x;

    dist[n] = INF; up[n] = X;
    for (i = 0; i < G[n].size(); i++)
    {
        x = G[n][i];
        if (x == t[n]) continue;

        dist[n] = minim(dist[n], dist[x]+1);
        up[n] = minim(up[n], up[x]-1);
    }

    if (dist[n] <= up[n])
        up[n] = INF;
    else
    {
        if (n == 1 || !up[n])
            dist[n] = 0, up[n] = INF;
    }
    
}

int check(int X)
/* cate check-pointuri sa puna minim a. i. distanta pana la cel
        mai apropiat check-point sa fie <= X */
{
    int i, cnt = 0;

    memset(dist, 0, sizeof(dist));
    memset(up, 0, sizeof(up));
    for (i = N; i >= 1; i--)
        compute(X, q[i]);

    for (i = 1; i <= N; i++)
        if (!dist[i])
            cnt++;
    return cnt;
}

int main(void)
{
    int i, u, v, qr, ql, st, dr, m, ok;
    
    freopen("salvare.in", "r", stdin);
    freopen("salvare.out", "w", stdout);

    scanf("%d %d", &N, &K);
    for (i = 1; i < N; i++)
    {
        scanf("%d %d", &u, &v);
        G[u].pb(v); G[v].pb(u);
    }

    for (q[qr=ql=1]=1, uz[1] = 1; qr <= ql; qr++)
        for (i = 0; i < G[q[qr]].size(); i++)
        {
            u = G[q[qr]][i];
            if (!uz[u])
            {
                uz[u] = 1;
                q[++ql] = u;
                t[u] = q[qr];
            }
        }

    st = 0; dr = N-1;
    while (st <= dr)
    {
        m = (st + dr) / 2;

        ok = check(m);
        if (ok <= K) bst = m, dr = m-1;
        else st = m+1;
    }

    ok = check(bst);
    ok = K-ok;
    for (i = 1; i <= N; i++)
        if (dist[i] && ok)
            dist[i] = 0, ok--;

    printf("%d\n", bst);
    for (i = 1; i <= N; i++)
        if (!dist[i])
            printf("%d ", i);
    printf("\n");

    return 0;
}