Cod sursa(job #1998818)

Utilizator preda.andreiPreda Andrei preda.andrei Data 9 iulie 2017 12:25:49
Problema Salvare Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

using Tree = vector<vector<int>>;

vector<int> GetNodes(const Tree &t, int max_time)
{
  vector<int> nodes;
  queue<int> q;

  vector<int> max_dist(t.size(), 0);
  vector<bool> visited(t.size(), false);

  for (size_t i = 0; i < t.size(); ++i) {
    if (t[i].size() == 1) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    int node = q.front();
    q.pop();

    if (visited[node]) {
      continue;
    }
    visited[node] = true;

    if (max_dist[node] == max_time) {
      nodes.push_back(node);
      max_dist[node] = 0;
    }

    for (int next : t[node]) {
      if (!visited[next]) {
        max_dist[next] = max(max_dist[next], max_dist[node] + 1);
        q.push(next);
      }
    }
  }
  return nodes;
}

int main()
{
  ifstream fin("salvare.in");
  ofstream fout("salvare.out");

  int nodes, k;
  fin >> nodes >> k;

  Tree tree(nodes);
  for (int i = 1; i < nodes; ++i) {
    int x, y;
    fin >> x >> y;
    tree[x - 1].push_back(y - 1);
    tree[y - 1].push_back(x - 1);
  }

  int res_time = 0;
  int power = (1 << 25);

  while (power > 0) {
    if ((int)GetNodes(tree, res_time + power).size() > k) {
      res_time += power;
    }
    power >>= 1;
  }

  ++res_time;
  auto res_nodes = GetNodes(tree, res_time);

  fout << res_time << "\n";
  for (int node : res_nodes) {
    fout << node + 1 << " ";
  }

  return 0;
}