Submission #1274321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274321		lucas110550	Migrations (IOI25_migrations)	C++20	10 / 100	30 ms	448 KiB

migrations

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

/*  ----------  research team side  ----------  */

static int storedN = -1;                     // current test case size
static vector<int> parent;                  // parent[i] = P[i]
static bool answered = false;               // have we already sent the answer
static int answerNode = 0;                  // deepest node (to send)

/* Called N-1 times, in order i = 1 .. N-1 */
int send_message(int N, int i, int Pi) {
    // first call of a new test case: initialise storage
    if (storedN != N) {
        storedN = N;
        parent.assign(N, -1);
        answered = false;
        answerNode = 0;
    }

    parent[i] = Pi;                         // remember the edge

    // we send a single message at the very last visited site
    if (i == N - 1 && !answered) {
        // compute depths (parent indices are always smaller)
        vector<int> depth(N, 0);
        for (int v = 1; v < N; ++v) {
            depth[v] = depth[parent[v]] + 1;
        }

        int best = 0, maxDepth = 0;
        for (int v = 0; v < N; ++v) {
            if (depth[v] > maxDepth) {
                maxDepth = depth[v];
                best = v;
            }
        }
        answerNode = best;                  // guaranteed best >= 1 by problem guarantee
        answered = true;
        // return the node index (1 .. 9999) as the message
        return answerNode;
    }

    // otherwise no message
    return 0;
}

/*  ----------  Museum side  ----------  */

pair<int,int> longest_path(vector<int> S) {
    int best = 0;
    for (int x : S) if (x != 0) best = x;   // the only non‑zero value
    // by construction best >= 1, and (0,best) is a longest pair
    return {0, best};
}

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