| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1274831 | mehrzad | Migrations (IOI25_migrations) | C++17 | 0 ms | 0 KiB |
#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"