Submission #1273672

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

migrations

#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
}


pair<int,int> longest_path(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};
}

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