Submission #1253732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253732		flashmt	Migrations (IOI25_migrations)	C++20	30 / 100	29 ms	460 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int N = 1e4;
const int Z = 4;

int furthest, d[N];

int send_message(int n, int i, int Pi) {
  d[i] = d[Pi] + 1;
  if (d[i] > d[furthest])
    furthest = i;

  if (i == n - 1)
    return furthest >= n - Z ? n - furthest : 0;

  if (i >= n - 3)
  {
    if (furthest >= n - 10)
    {
      for (int j = n - 3, val = furthest - (n - 10); j < n - 1; j++)
      {
        if (j == i)
          return val % Z + 1;
        val /= Z;
      }
    }
    return 0;
  }

  if (i >= n - 10)
  {
    for (int j = n - 10, val = furthest; j < n - 3; j++)
    {
      if (j == i)
        return val % Z + 1;
      val /= Z;
    }
  }

  return 0;
}

pair<int, int> longest_path(vector<int> s)
{
  int n = size(s);
  if (s[n - 1])
    return {0, n - s[n - 1]};

  int u = 0, isBad = 0;
  for (int i = n - 2; i >= n - 3; i--)
    if (!s[i]) isBad = 1;
    else u = u * Z + s[i] - 1;

  if (!isBad)
    return {0, u + n - 10};

  int v = 0;
  for (int i = n - 4; i >= n - 10; i--)
    v = v * Z + s[i] - 1;
  return {0, v};
}

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