Submission #1274832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274832		mehrzad	Migrations (IOI25_migrations)	C++17	10 / 100	28 ms	448 KiB

migrations

#include "migrations.h"
#include <vector>
#include <utility>

// ------- Persistent state across send_message calls within the first run -------
namespace {
  static int depth_arr[10005];
  static int bestV = 0;
  static int bestD = 0;
  static bool initialized = false;
}

// Research team procedure
int send_message(int N, int i, int Pi) {
  if (!initialized) {
    initialized = true;
    depth_arr[0] = 0;
    bestV = 0;
    bestD = 0;
  }

  // Compute depth of current node i (since P[i] < i, depth[Pi] is already known)
  depth_arr[i] = depth_arr[Pi] + 1;

  // Track deepest node from root (site 0)
  if (depth_arr[i] > bestD) {
    bestD = depth_arr[i];
    bestV = i;
  }

  // Send exactly one message at the last site: encode bestV as bestV+1
  if (i == N - 1) {
    return bestV + 1; // in [1..N] ≤ 10000 ≤ 20000
  }
  return 0;
}

// Museum procedure
std::pair<int,int> longest_path(std::vector<int> S) {
  int N = (int)S.size();
  int last_nonzero_idx = -1;
  for (int i = 1; i < N; ++i) if (S[i] != 0) last_nonzero_idx = i;

  if (last_nonzero_idx == -1) {
    // Fallback (no message found)
    return {0, 0};
  }
  int code = S[last_nonzero_idx]; // expected: bestV+1
  int v = code - 1;
  return {0, v};
}

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