제출 #1274831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274831		mehrzad	이주 (IOI25_migrations)	C++17	컴파일 에러	0 ms	0 KiB

migrations

#include <bits/stdc++.h>
using namespace std;

/*
  Strategy (targets Subtask 1 correctness):
  - Maintain depths from root (site 0). Since P[i] < i and calls come in increasing i,
    we can compute depth[i] = depth[P[i]] + 1 online.
  - Track the deepest node seen so far; let it be bestV with depth bestD.
  - Send NO messages until the very last call (i == N-1). On that last call, send bestV+1.
    (Indices are 0..N-1, so bestV+1 fits in [1..10000] for N=10000, thus ≤ 20000.)
  - Museum: read the last non-zero entry in S and return (0, value-1) as the diameter endpoints.

  Notes:
  - This solution is guaranteed correct for Subtask 1 (where one endpoint of the diameter is site 0).
  - It uses a single message (M = 1) and Z ≤ 10000.
*/

// ------- Persistent state across send_message calls within the first run -------
namespace {
  // We assume N ≤ 10000, so this static storage is fine.
  static int depth_arr[10005];
  static int bestV = 0;
  static int bestD = 0;
  static bool initialized = false;
  static int N_cached = 0;
}

extern "C" {

// Research team procedure
int send_message(int N, int i, int Pi) {
  if (!initialized) {
    // Initialize on first call of each test case
    initialized = true;
    N_cached = N;
    depth_arr[0] = 0;
    bestV = 0;
    bestD = 0;
  }

  // Compute depth of current node i
  depth_arr[i] = depth_arr[Pi] + 1;

  // Update deepest node rooted at 0
  if (depth_arr[i] > bestD) {
    bestD = depth_arr[i];
    bestV = i;
  }

  // Only send the answer (encoded) at the final call
  if (i == N - 1) {
    // Encode bestV (0..N-1) as bestV+1 in [1..N], fits ≤ 10000 ≤ 20000
    int code = bestV + 1;
    return code;
  }
  return 0;
}

// Museum procedure
pair<int,int> longest_path(vector<int> S) {
  // Find the last non-zero message (we send exactly one, at i = N-1, but be robust)
  int N = (int)S.size();
  int last = 0;
  for (int i = 1; i < N; ++i) {
    if (S[i] != 0) last = i;
  }
  int code = S[last]; // should be bestV+1 if our protocol ran
  if (code <= 0) {
    // Fallback (no message) — return trivial pair
    return {0, 0};
  }
  int v = code - 1;
  return {0, v};
}

} // extern "C"

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccbEyD9j.o: in function `main':
stub.cpp:(.text.startup+0xa9): undefined reference to `send_message(int, int, int)'
/usr/bin/ld: stub.cpp:(.text.startup+0x230): undefined reference to `longest_path(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status