제출 #1292358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292358		cnam9	이주 (IOI25_migrations)	C++20	30 / 100	34 ms	448 KiB

migrations

#include <vector>

using namespace std;

constexpr int N = 1e4;

int checkpoint;
pair<int, int> maxopt = {0, 0};
int depth[N] = {0};
bool highly[N];

void init(int n) {
    maxopt = {0, 0};
    depth[0] = 0;
}

int send_message(int n, int i, int p) {

    if (i == n - 14) {
        checkpoint = maxopt.second;
    }

    highly[i] = false;
    depth[i] = depth[p] + 1;
    if (depth[i] > maxopt.first) {
        maxopt.first = depth[i];
        maxopt.second = i;
        highly[i] = true;
    }

    if (i < n - 14) {
        return 0;
    }
    if (i < n - 7) {
        return 1 + ((checkpoint >> 2 * (i - (n - 14))) & 3);
    }
    int d = n - 1 - i;
    return 1 + highly[n - 1 - 2 * d - 1] + 2 * highly[n - 1 - 2 * d];
}


pair<int, int> longest_path(vector<int> S) {
    int n = S.size();

    int opt = 0;
    for (int i = n - 14; i < n - 7; i++) {
        opt |= (S[i] - 1) << 2 * (i - (n - 14));
    }
    for (int i = n - 7; i < n; i++) {
        int d = n - 1 - i;
        if ((S[i] - 1) & 1)
            opt = n - 1 - 2 * d - 1;
        if ((S[i] - 1) & 2)
            opt = n - 1 - 2 * d;
    }
    return {0, opt};
}

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