Submission #1276429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276429		seannaren	Migrations (IOI25_migrations)	C++17	10 / 100	29 ms	448 KiB

migrations

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

/*  send_message:
    called N-1 times, in order i = 1 .. N-1.
    Must return 0 (no message) or an integer 1..20000.
    At most 50 non‑zero returns are allowed.
*/
int send_message(int N, int i, int Pi) {
    // static data that persists between calls
    static bool initialized = false;
    static int totalN = 0;
    static vector<int> depth;
    static int bestDepth = -1;
    static int bestNode = -1;   // deepest vertex seen so far

    if (!initialized) {
        // first call – allocate structures
        totalN = N;
        depth.assign(N, -1);
        depth[0] = 0;           // root
        bestDepth = 0;
        bestNode = 0;
        initialized = true;
    }

    // compute depth of current vertex i
    depth[i] = depth[Pi] + 1;

    // update deepest vertex if needed
    if (depth[i] > bestDepth) {
        bestDepth = depth[i];
        bestNode = i;
    }

    // send a message only at the last vertex
    if (i == totalN - 1) {
        // deepest vertex is always >0 when N>1
        if (bestNode == 0) return 0;          // N == 1 case (should not happen)
        return bestNode;                       // 1 .. 9999  (< 20000)
    }

    // otherwise, send nothing
    return 0;
}

/*  longest_path:
    receives the whole array S (size N, S[0]=0), where S[i] is the value
    returned by send_message at site i.
    Must return a pair of vertices forming a diameter.
*/
pair<int,int> longest_path(vector<int> S) {
    int deepest = -1;
    for (size_t i = 0; i < S.size(); ++i) {
        if (S[i] != 0) deepest = S[i];
    }
    if (deepest == -1) {
        // N == 1 : only vertex 0 exists
        return {0, 0};
    }
    // By the problem promise, (0, deepest) is a correct diameter pair
    return {0, deepest};
}

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