Submission #1275594

#TimeUsernameProblemLanguageResultExecution timeMemory
1275594mehrzadMigrations (IOI25_migrations)C++17
0 / 100
33 ms1168 KiB
#include "migrations.h" #include <vector> #include <utility> #include <algorithm> using namespace std; /* Robust + low-Z tail streaming (works for all trees; hits Subtask 1 = 30 when feasible): - Maintain diameter endpoints (A,B) online via bounded LCA. - Tail window W=50: * On first entry: emit a RESET (0) [0 means "no message"; allowed] * Then stream 14 base-4 digits (values 1..4) encoding (A,B) interleaved LSB-first: positions 0..13: a0,b0,a1,b1,...,a6,b6 where ax/bx are base-4 digits of A/B. * If the diameter changes at index i: - If slots_left >= 14: emit RESET (0) and restart streaming for the new (A,B). - Else (too late): emit a single FALLBACK message = 10000 + (other+1). - Museum: * If any S[i] > 4 in the tail exists → return (i, S[i]-10000-1). * Else decode after the last RESET: read the FIRST 14 digits (1..4) that follow and reconstruct (A,B). */ namespace { // Per-test state bool inited = false; int Nglob = 0, LOGv = 0; const int W = 50; int tailStart = 1; // LCA tables vector<int> depth; vector< vector<int> > up; // up[v][k] // Online diameter int A = 0, B = 0, D = 0; // Tail streaming state bool have_reset = false; int stream_pos = -1; // 0..13 for 14 digits inline void reset_case(int N){ inited = true; Nglob = N; LOGv = 0; while ((1 << LOGv) <= (Nglob > 0 ? Nglob : 1)) ++LOGv; depth.assign(Nglob, 0); up.assign(Nglob, vector<int>(LOGv, 0)); for (int k = 0; k < LOGv; ++k) up[0][k] = 0; A = B = 0; D = 0; tailStart = max(1, Nglob - W); have_reset = false; stream_pos = -1; } inline int lca(int u, int v){ if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int k = 0; k < LOGv; ++k) if (diff & (1 << k)) u = up[u][k]; if (u == v) return u; for (int k = LOGv - 1; k >= 0; --k){ if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; } } return up[u][0]; } inline int dist(int u, int v){ int w = lca(u, v); return depth[u] + depth[v] - 2 * depth[w]; } inline int digit_base4(int x, int d){ // d-th digit (LSB-first), 0..3 return (x >> (2*d)) & 3; } } int send_message(int N, int i, int Pi){ // Reinit at the start of each test if (!inited || i == 1) reset_case(N); // Build LCA info for node i depth[i] = depth[Pi] + 1; up[i][0] = Pi; for (int k = 1; k < LOGv; ++k) up[i][k] = up[ up[i][k-1] ][k-1]; // Online diameter update int dA = dist(i, A); int dB = dist(i, B); bool changed = false; int other = -1; if (dA > D){ changed = true; other = A; B = i; D = dA; } else if (dB > D){ changed = true; other = B; A = i; D = dB; } int out = 0; if (i >= tailStart){ if (!have_reset){ // Start tail epoch have_reset = true; stream_pos = 0; return 0; // RESET (no message) } if (changed){ int slots_left = (Nglob - 1) - i; // remaining indices after i if (slots_left >= 14){ // Enough room to re-encode final diameter stream_pos = 0; return 0; // RESET } else { // Too late to finish 14 digits → guarantee correctness with one fallback message // Encodes 'other' so Museum can return (i, other) return 10000 + (other + 1); // ≤ 20000 since other+1 ≤ 10000 } } // No change → stream digits for current (A,B) if (stream_pos >= 0 && stream_pos < 14){ int which = stream_pos++; int dig = ((which & 1) ? digit_base4(B, which/2) : digit_base4(A, which/2)); // 0..3 out = dig + 1; // map to 1..4 to keep Z ≤ 4 } else { out = 0; // no padding — silence after 14 digits } } return out; // 0..20000 } std::pair<int,int> longest_path(std::vector<int> S){ int N = (int)S.size(); int tail = max(1, N - 50); // If any fallback (>4) exists in the tail, last one wins for (int i = N - 1; i >= tail; --i){ if (S[i] > 4){ int other = S[i] - 10000 - 1; if (other < 0) other = 0; if (other >= N) other = N - 1; return { i, other }; } } // Otherwise decode after the last RESET (0) int lastReset = -1; for (int i = N - 1; i >= tail; --i){ if (S[i] == 0){ lastReset = i; break; } } if (lastReset == -1){ // Extremely unlikely; safe fallback return {0, 0}; } // Read the FIRST 14 digits (1..4) after the last reset int cnt = 0; int Arec = 0, Brec = 0; for (int i = lastReset + 1; i < N && cnt < 14; ++i){ int v = S[i]; if (1 <= v && v <= 4){ int d = v - 1; // 0..3 if ((cnt & 1) == 0){ // A digit int k = cnt / 2; Arec |= (d << (2*k)); } else { // B digit int k = cnt / 2; Brec |= (d << (2*k)); } ++cnt; } } if (Arec >= N) Arec = N - 1; if (Brec >= N) Brec = N - 1; return {Arec, Brec}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...