제출 #1326167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326167		jack112739	Migrations (IOI25_migrations)	C++20	0 / 100	33 ms	1184 KiB

migrations

#if 0
#include "migration.h"
#else

#endif

#include <algorithm>
#include <vector>
using namespace std;

vector<int> tree[10005];
pair<int, int> depth[10005];
int last[30], id11[3000], a1, a2, ta1, ta2, len = -1;

void dfs_depth(int u, int par, int d) {
    depth[u] = {0, 0};
    if(tree[u].size() == 1) depth[u] = {d, u};
    for(int child: tree[u]) if(child != par) {
        dfs_depth(child, u, d + 1);
        depth[u] = max(depth[u], depth[child]);
    }
}
void reset_a1a2(int n) {
    dfs_depth(n, n, 0);
    if(len == -1) {
        a1 = depth[n].second;
        dfs_depth(a1, a1, 0);
        a2 = depth[a1].second;
        len = depth[a1].first;
        return;
    }
    if(tree[a1].size() == 1 && depth[a1].first > len) len++, a2 = n;
    if(tree[a2].size() == 1 && depth[a2].first > len) len++, a1 = n; 
}
void encode_last11(int num, int *to) {
    int rem = num % 64, dv = num / 64;
    for(int i = 0; i < (1 << 11); i++) if(__builtin_popcount(i) == 3) {
        dv--;
        if(dv == 0) {
            for(int j = 0; j < 11; j++) if(i & (1 << j)) to[j] = 1 + (rem %4), rem /= 4;
            break;
        }
    }
}
int decode_last11(int *from) {
    int mask = 0, rem = 0, cnt = 0;
    for(int j = 10; j >= 0; j--) if(from[j] != 0) {
        mask |= (1 << j);
        rem = 4 * rem + from[j] - 1;
    }
    for(int i = 0; i < (1 << 11); i++) if(__builtin_popcount(i) == 3) {
        if(i == mask) break;
        cnt++;
    }
    return cnt * 64 + rem;
}

int send_message(int N, int i, int Pi) {
    tree[Pi].push_back(i);
    tree[i].push_back(Pi);
    N--;
    if(i <= N - 28) return 0;
    reset_a1a2(i); 
    if(i == N - 27) encode_last11(a2, last + 17), ta2 = a2;
    if(i == N - 16) encode_last11(a1, last + 6), ta1 = a1;
    if(i == N - 5 && a2 != ta2) {
        int mask = (N - 4) - a2; 
        ta2 = a2;
        last[5] = mask / 5, last[ 4] = mask % 5;
    }
    if(i == N - 3 && a1 != ta1) {
        int mask = (N - 2) - a1; 
        ta1 = a1;
        last[3] = mask / 4, last[2] = mask % 4;
    }
    if(i == N - 2 && a1 == i) last[2] = 4, ta1 = a1;
    if(i == N - 1 && a2 != ta2) ta2 = a2, last[1] = N - a2;
    if(i == N) {
        if(a1 == N) last[0] = 1;
        if(a2 == N && a1 == ta1) last[0] = 2;
        if(a1 == N - 1 && a2 == ta2) last[0] = 3;
        if(a1 == N - 1 && a2 == N) last[0] = 4;
    } 
    return last[N - i];
}
pair<int, int> longest_path(vector<int> S) {
    int N = S.size() - 1;
    for(int i = 0; i < min(N,28); i++) last[i] = S[N - i];
    a2 = decode_last11(last + 17);
    a1 = decode_last11(last + 6);
    if(last[5] != 0 || last[4] != 0) a2 = (N - 4) - 5 * last[5] - last[4];
    if(last[2] == 4) a1 = N - 2;
    else if(last[3] != 0 || last[2] != 0) a1 = (N - 2) - last[3] * 4 - last[2];
    if(last[1] != 0) a2 = N - last[1];
    if(last[0] == 1) a1 = N;
    if(last[0] == 2) a2 = N;
    if(last[0] == 3) a1 = N - 1;
    if(last[0] == 4) a1 = N - 1, a2 = N;
    return {a1, a2};
}

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