Submission #1258171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258171		ogkostya	Migrations (IOI25_migrations)	C++20	10 / 100	29 ms	1028 KiB

migrations

#include "migrations.h"
#include <queue>

std::vector<std::vector<int>> nn;

int send_message(int N, int i, int Pi)
{
  if (nn.size() == 0)
  {
    nn = std::vector<std::vector<int>>(N, std::vector<int>());
  }
  nn[i].push_back(Pi);
  nn[Pi].push_back(i);

  if (i == N - 1)
  {
    std::queue<int> q;
    q.push(0);
    std::vector<int> d(N, -1);
    while (q.size() > 0)
    {
      int j = q.front();
      q.pop();

      for (int k : nn[j])
      {
        if (d[k] == -1)
        {
          d[k] = 1 + d[j];
          q.push(k);
        }
      }
    }
    int max = 0;
    for (int j = 1; j < N; j++)
      if (d[max] < d[j])
        max = j;

    return max;
  }
  else
  {
    return 0;
  }
}

std::pair<int, int> longest_path(std::vector<int> S)
{
  return {0, S.back()};
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 30
• Subtask 2: 0 / 70