| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1273671 | lucas110550 | Migrations (IOI25_migrations) | C++20 | 0 ms | 0 KiB |
#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/* -------------------------------------------------------------
Global state used by the team while processing the calls.
It is cleared automatically on each program run.
------------------------------------------------------------- */
static int N_global = 0;
static vector<int> depth; // depth[i] = distance from root 0
static int maxDepth = -1; // current maximal depth
static int maxNode = -1; // node achieving maxDepth
static bool initialized = false;
/* -------------------------------------------------------------
send_message
Called N‑1 times, with i = 1 … N‑1, Pi being the parent of i.
Returns 0 (no message) or a positive integer (the only message).
------------------------------------------------------------- */
int send_message(int N, int i, int Pi) {
if (!initialized) {
N_global = N;
depth.assign(N_global, 0); // depth[0] = 0 already
maxDepth = 0;
maxNode = 0;
initialized = true;
}
// compute depth of the current node
depth[i] = depth[Pi] + 1;
if (depth[i] > maxDepth) {
maxDepth = depth[i];
maxNode = i;
}
// send the answer only at the very last site
if (i == N_global - 1) {
// encode deepest node id + 1 (always 1 … 20000)
return maxNode + 1;
}
return 0; // no message
}
/* -------------------------------------------------------------
longest_path
Called once after all send_message calls.
Receives the whole array S[0 … N‑1] (S[0] = 0).
Must return a pair of sites with maximum distance.
------------------------------------------------------------- */
pair<int,int> longest_path(const vector<int>& S) {
int leaf = -1;
for (size_t i = 0; i < S.size(); ++i) {
if (S[i] != 0) { // there is exactly one such entry
leaf = S[i] - 1; // decode deepest node
}
}
if (leaf == -1) leaf = 0; // safety, should never happen
return {0, leaf};
}