Submission #1258200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258200		ogkostya	Migrations (IOI25_migrations)	C++20	30 / 100	29 ms	1068 KiB

migrations

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

std::vector<std::vector<int>> nn;
std::vector<int> d(1, 0);
int max = 0;
std::vector<int> p1;
std::vector<int> p2;

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);
  d.push_back(1 + d[Pi]);
  max = std::max(max, d.back());

  if (i == N - 1)
  {
    if (d[N - 1] == max)
      return 1;
    if (d[N - 2] == max)
      return 2;
    if (d[N - 3] == max)
      return 3;
    if (d[N - 4] == max)
      return 4;
    return 0;
  }
  else if (i >= N - 3)
  {
    if (p1.size() == 0)
    {
      p1.push_back(0);
      p1.push_back(0);
      for (int j = 4; j <= 24; j++)
      {
        if (max == d[N - j])
        {
          p1[0] = j / 5;
          p1[1] = j % 5;
          break;
        }
      }
    }
    return p1[i - (N - 3)];
  }
  else if (i >= N - 9)
  {
    if (p2.size() == 0)
    {
      for (int j = 0; j < 6; j++)
        p2.push_back(0);

      for (int j = i; j >= 0; j--)
        if (d[j] == max)
        {
          for (int k = 5; k >= 0 && j > 0; k--)
          {
            p2[k] = j % 5;
            j /= 5;
          }
          break;
        }
    }
    return p2[i - (N - 9)];
  }
  else
  {
    return 0;
  }
}

std::pair<int, int> longest_path(std::vector<int> S)
{
  int n = S.size();
  if (S[n - 1] != 0)
  {
    return {0, n - S[n - 1]};
  }
  if (S[n - 2] != 0 || S[n - 3] != 0)
  {
    return {0, n - (S[n - 3] * 5 + S[n - 2])};
  }
  int ans = 0;
  for (int i = n - 9, k = 0; k < 6; i++, k++)
  {
    ans *= 5;
    ans += S[i];
  }
  return {0, ans};
}

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