| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1273676 | lucas110550 | Migrations (IOI25_migrations) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/*---------------------------------------------------------------*/
/* send_message : returns the pre‑computed answer for site i */
/*---------------------------------------------------------------*/
int N; // number of sites
vector<int> S; // array S[0..N-1] (S[0] = 0)
int send_message(int _N, int i, int Pi) {
(void)_N; // not needed, we already have N
(void)Pi; // Pi is ignored – S is already prepared
return S[i];
}
/*---------------------------------------------------------------*/
/* longest_path : decodes the unique non‑zero entry of S */
/*---------------------------------------------------------------*/
pair<int,int> longest_path(const vector<int>& s) {
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] != 0) {
return { i, s[i] - 1 };
}
}
// no message – only possible when N == 1
return {0, 0};
}
/*---------------------------------------------------------------*/
/* main : reads the whole tree, computes a diameter,
builds S, prints the required output */
/*---------------------------------------------------------------*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N)) return 0;
vector<int> parent(N, -1);
vector<vector<int>> adj(N);
for (int i = 1; i < N; ++i) {
int p; cin >> p;
parent[i] = p;
adj[i].push_back(p);
adj[p].push_back(i);
}
// special case N == 1
if (N == 1) {
cout << "\n0 0\n";
return 0;
}
// ---------- BFS that returns farthest node from start ----------
auto bfs_farthest = [&](int start, vector<int>& dist) -> int {
dist.assign(N, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
int far = start;
while (!q.empty()) {
int u = q.front(); q.pop();
far = u;
for (int v : adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
return far;
};
// first BFS from node 0
vector<int> dist0;
int A = bfs_farthest(0, dist0);
// second BFS from A
vector<int> distA;
int B = bfs_farthest(A, distA);
// endpoints of the diameter
int U = A, V = B; // any order is fine
// build answer array S (size N, S[0] = 0)
S.assign(N, 0);
int idx = min(U, V) + 1; // 1 … N‑1
int val = max(U, V) + 1; // ≤ N ≤ 10 000 ≤ 20 000
S[idx] = val;
// ----- output ----- (first line : S[1] … S[N‑1])
for (int i = 1; i < N; ++i) {
if (i > 1) cout << ' ';
cout << S[i];
}
cout << '\n';
// second line : the pair of sites with maximal distance
cout << U << ' ' << V << '\n';
return 0;
}