Submission #1275592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275592		mehrzad	Migrations (IOI25_migrations)	C++17	0 / 100	30 ms	444 KiB

migrations

#include "migrations.h"
#include <vector>
#include <utility>
using namespace std;

/*
Subtask-1 optimized strategy (diameter includes site 0):
Goal: Z <= 4 (full 30 pts) whenever final deepest site appears by i <= N-8.
- Track depth[i] = depth[Pi] + 1, and keep BEST = argmax depth.
- In the last window W (<=50), we transmit BEST using *only* digits 1..4:
    * Use RESET marker = 0 (does not count toward Z).
    * Encode BEST in base-4, LSB-first, 7 digits total (since 4^7 >= 10000).
    * After RESET, send exactly the first 7 digits (no padding). Stay silent afterward.
- If BEST changes inside the window:
    * If slots_left >= 7: send RESET and restart the 7-digit stream for the new BEST.
    * If slots_left < 7 (too late): send ONE fallback message = 10000 + (BEST+1) to guarantee correctness.
Museum:
- Prefer the last value > 4 in the tail window (fallback): decode BEST = val-10000-1 and return (0, BEST).
- Otherwise take the last RESET (0) in the tail and read the FIRST 7 digits (1..4) that follow to reconstruct BEST, then return (0, BEST).

Notes:
- This code is specialized for Subtask 1. It does not solve the general case where the diameter endpoints may not include 0.
- Z <= 4 and M <= W (<= 50) in the common case; worst-case uses a single fallback but stays correct.
*/

namespace {
    // Persistent per-test state for send_message
    bool inited = false;
    int Nglob = 0;

    // depth and current best (farthest from 0 by depth)
    std::vector<int> depth;
    int BEST = 0;         // site index with maximum depth so far
    int BEST_depth = 0;   // its depth

    // Tail window parameters
    const int W = 50;     // use full allowance; you may reduce to ~16-24 if desired
    int tailStart = 1;

    // Streaming state
    bool have_reset = false;
    int stream_pos = -1;  // 0..6 for 7 base-4 digits; -1 means not streaming yet

    inline void reset_test(int N) {
        inited = true;
        Nglob = N;
        depth.assign(Nglob, 0);
        BEST = 0;
        BEST_depth = 0;        // depth[0] = 0
        tailStart = (Nglob >= 2) ? max(1, Nglob - W) : 1;
        have_reset = false;
        stream_pos = -1;
    }

    inline int base4_digit(int x, int d){ // d-th digit (LSB-first), returns 0..3
        return (x >> (2*d)) & 3;
    }
}

int send_message(int N, int i, int Pi) {
    if (!inited || i == 1) reset_test(N);

    // Update depth and maintain BEST (strictly greater depth only, to keep BEST stable once max depth is reached)
    depth[i] = depth[Pi] + 1;
    if (depth[i] > BEST_depth) {
        BEST_depth = depth[i];
        BEST = i;
    }

    int out = 0; // default: no message

    if (i >= tailStart) {
        // Ensure exactly one RESET at the start of the tail window
        if (!have_reset) {
            have_reset = true;
            stream_pos = 0;
            return 0; // RESET marker (doesn't affect Z)
        }

        // If BEST changed at this step, decide whether we can restart a full 7-digit stream
        // (Note: we track BEST via depth and it can change multiple times.)
        // Compute remaining slots after this index:
        int slots_left = (Nglob - 1) - i;

        // Detect if BEST was updated now by checking if this i is the current BEST and just matched BEST_depth
        // (A simpler proxy: recompute "is this node at depth == BEST_depth and index == BEST?")
        bool best_just_now = (i == BEST);

        if (best_just_now) {
            if (slots_left >= 7) {
                // Safe to restart a full stream for the new BEST
                stream_pos = 0;
                return 0; // RESET
            } else {
                // Too late to send 7 digits → fallback once with big value encoding BEST directly
                // Encode BEST+1 as 10000 + (BEST+1) (<= 20000 since BEST+1 <= 10000)
                return 10000 + (BEST + 1);
            }
        }

        // No new BEST at this step → emit digits if we still owe the 7-digit payload
        if (stream_pos >= 0 && stream_pos < 7) {
            int d = base4_digit(BEST, stream_pos); // 0..3
            out = d + 1;                           // map to 1..4 (keeps Z <= 4)
            ++stream_pos;
        } else {
            out = 0; // already sent 7 digits or not streaming → stay silent
        }
    }

    return out; // 0..20000
}

std::pair<int,int> longest_path(std::vector<int> S) {
    int N = (int)S.size();
    int tailStart = (N >= 2) ? max(1, N - 50) : 1;

    // 1) Fallback takes precedence if present
    for (int i = N - 1; i >= tailStart; --i) {
        if (S[i] > 4) {
            int best = S[i] - 10000 - 1;
            if (best < 0) best = 0;
            if (best >= N) best = N - 1;
            return {0, best};
        }
    }

    // 2) Otherwise decode after the last RESET (0)
    int lastReset = -1;
    for (int i = N - 1; i >= tailStart; --i) {
        if (S[i] == 0) { lastReset = i; break; }
    }

    int best = 0;
    if (lastReset != -1) {
        // Read FIRST 7 digits (1..4) after last reset
        int pos = 0;
        for (int i = lastReset + 1; i < N && pos < 7; ++i) {
            if (S[i] >= 1 && S[i] <= 4) {
                int d = S[i] - 1; // 0..3
                best |= (d << (2 * pos));
                ++pos;
            }
        }
        // If fewer than 7 were found (shouldn't happen with our emission policy), the missing high digits stay 0.
    }
    return {0, best};
}

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