Cod sursa(job #2441797)

Utilizator CharacterMeCharacter Me CharacterMe Data 21 iulie 2019 11:11:01
Problema Salvare Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <cstdio>
#include <vector>
using std::vector; using std::min; using std::max;
int n, k, i, j, dist[1001], cnt;
vector<int> graph[1001];
bool house[1001];
void dfs(int node, int dad, int val);
int main()
{
    freopen("salvare.in", "r", stdin);
    freopen("salvare.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(i=1; i<n; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int l, r, mid;
    l=0; r=2*n;
    while(l<=r){
        mid=(l+r)/2; cnt=0;
        dfs(1, 0, mid);
        if(dist[1]>=0) {++cnt; house[1]=true;}
        if(cnt>k) l=mid+1;
        else r=mid-1;
    }
    printf("%d\n", l);
    cnt=0; for(i=1; i<=n; ++i) house[i]=false;
    dfs(1, 0, l);
    if(dist[1]>=0) {++cnt; house[1]=true;}
    for(i=1; i<=n; ++i) if(house[i]==true) printf("%d ", i);
    return 0;
}
void dfs(int node, int dad, int val){
    dist[node]=0; int furthest=0, closest=3000001;
    for(auto i:graph[node]) if(i!=dad){
        dfs(i, node, val);
        furthest=max(furthest, dist[i]+1);
        closest=min(closest, dist[i]+1);
    }
    dist[node]=furthest;
    if(dist[node]==val){house[node]=true; ++cnt; dist[node]=-val-1; return;}
    if(closest<0 && -closest-1>=dist[node]) dist[node]=closest;
    return;
}