제출 #1273673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273673		lucas110550	이주 (IOI25_migrations)	C++20	20 / 100	43 ms	912 KiB

migrations

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

const int LOG = 15;                             // 2^14 = 16384 > 10000

// ---------- global state for the incremental construction ----------
static int gN = -1;
static vector<int> gDepth;
static vector<array<int, LOG>> gUp;
static int gA = 0, gB = 0, gD = 0; // current diameter endpoints and length
static int gAprev = -1, gBprev = -1; // endpoints after processing N-2

// ---------- LCA utilities ----------
int lca(int u, int v) {
        if (gDepth[u] < gDepth[v]) swap(u, v);
        int diff = gDepth[u] - gDepth[v];
        for (int k = LOG - 1; k >= 0; --k)
                if (diff & (1 << k))
                        u = gUp[u][k];
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; --k) {
                if (gUp[u][k] != gUp[v][k]) {
                        u = gUp[u][k];
                        v = gUp[v][k];
                }
        }
        return gUp[u][0];
}
int dist(int u, int v) {
        int w = lca(u, v);
        return gDepth[u] + gDepth[v] - 2 * gDepth[w];
}

// ---------- send_message implementation ----------
int send_message(int N, int i, int Pi) {
        // (re)initialise for a new test case
        if (gN != N) {
                gN = N;
                gDepth.assign(N, 0);
                gUp.assign(N, array<int, LOG>());
                for (int k = 0; k < LOG; ++k) gUp[0][k] = 0;
                gA = gB = 0;
                gD = 0;
                gAprev = gBprev = -1;
        }

        // set depth and binary lifting ancestors for node i
        gDepth[i] = gDepth[Pi] + 1;
        gUp[i][0] = Pi;
        for (int k = 1; k < LOG; ++k)
                gUp[i][k] = gUp[gUp[i][k - 1]][k - 1];

        // update the diameter using the new node i
        int da = dist(i, gA);
        int db = dist(i, gB);
        if (da > gD) {
                gB = i;
                gD = da;
        } else if (db > gD) {
                gA = i;
                gD = db;
        }

        // node N-2: remember the current endpoints and send the first endpoint
        if (i == N - 2) {
                gAprev = gA;
                gBprev = gB;
                return gA + 1;                                   // encode a+1 (always 1..10000)
        }

        // node N-1: we now know the final diameter, encode the second endpoint / flag
        if (i == N - 1) {
                bool unchanged = ( (gA == gAprev && gB == gBprev) ||
                                                   (gA == gBprev && gB == gAprev) );
                if (unchanged) {
                        // unchanged: send bprev+1  (<=10000)
                        return gBprev + 1;
                } else if ( (gA == N - 1 && gB == gAprev) ||
                                        (gB == N - 1 && gA == gAprev) ) {
                        // new leaf paired with a_prev -> (N-1, a_prev)
                        // encode by sending nothing
                        return 0;
                } else {
                        // new leaf paired with b_prev -> (N-1, b_prev)
                        // encode as bprev + 10001 (range 10001..19999)
                        return gBprev + 10001;
                }
        }

        // any other node: we do not send a message
        return 0;
}

// ---------- longest_path implementation ----------
pair<int, int> longest_path(vector<int> S) {
        int N = (int)S.size();                          // S[0] is always 0
        int a = S[N - 2] - 1;                             // first endpoint stored at N-2
        int v = S[N - 1];                                         // second part / flag

        int u, w;
        if (v == 0) {                                             // (N-1, a)
                u = a;
                w = N - 1;
        } else if (v <= 10000) {                           // unchanged case (a, b)
                u = a;
                w = v - 1;
        } else {                                                           // (N-1, b)
                u = N - 1;
                w = v - 10001;
        }
        return {u, w};
}

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