제출 #1251759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251759		fv3	Migrations (IOI25_migrations)	C++20	72.89 / 100	685 ms	1408 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 10000;
vector<vector<int>> adj(N);

int diameter = 0;
int ai = 0, bi = 0;

bool Aknown = false;
bool Bknown = false;

int Abit = 0;
int Bbit = 0;

int send_message(int N_, int i, int Pi) {
    assert(N_ == 10000);

    adj[i].push_back(Pi);
    adj[Pi].push_back(i);

    vector<int> dist(i + 1), vis(i + 1);
    auto Dfs = [&](auto&& self, int j) -> void {
        vis[j] = 1;
        for (auto node : adj[j]) {
            if (vis[node]) continue;
            dist[node] = dist[j] + 1;
            self(self, node);
        }
    };
    Dfs(Dfs, i);

    if (dist[ai] > diameter) {
        bi = i;
        diameter = dist[ai];
    } else if (dist[bi] > diameter) {
        ai = i;
        diameter = dist[bi];
    }

    if (i >= N - 28) {
        if (Abit >= 14) Aknown = true;
        if (Bbit >= 14) Bknown = true;

        if (Aknown && Bknown) {
            if (ai == i) {
                return 1;
            } else if (bi == i) {
                return 2;
            }
            return 0;
        }

        if (!Aknown && !Bknown) {
            if (ai == i) {
                Aknown = true;
                return 2;
            } 
            if (bi == i) {
                Bknown = true;
                return 3;
            }

            return ((ai & (1 << Abit++)) ? 1 : 0);
        }

        if (ai == i) {
            if (!Aknown) {
                Aknown = true;
                return 4;
            }
            return (2 | ((bi & (1 << Bbit++)) ? 1 : 0));
        } else if (bi == i) {
            if (!Bknown) {
                Bknown = true;
                return 4;
            } 
            return (2 | ((ai & (1 << Abit++)) ? 1 : 0));
        }

        if (!Aknown) {
            return ((ai & (1 << Abit++)) ? 1 : 0);
        } else if (!Bknown) {
            return ((bi & (1 << Bbit++)) ? 1 : 0);
        }
    }

    return 0;
}

pair<int, int> longest_path(vector<int> S) {
    int A = 0, B = 0;
    bool isAknown = false;
    bool isBknown = false;

    int bitA = 0;
    int bitB = 0;

    for (int i = N - 28; i < N; i++) {
        if (bitA >= 14) isAknown = true;
        if (bitB >= 14) isBknown = true;

        if (isAknown && isBknown) {
            if (S[i] == 1) {
                A = i;
            } else if (S[i] == 2) {
                B = i;
            } else {
                assert(S[i] == 0);
            }
            continue;
        }

        if (!isAknown && !isBknown) {
            if (S[i] == 2) {
                A = i;
                isAknown = true;
                continue;
            }
            if (S[i] == 3) {
                B = i;
                isBknown = true;
                continue;
            }

            A |= (S[i] << bitA++);
            continue;
        }

        if (S[i] == 4) {
            if (!isBknown) {
                isBknown = true;
                B = i;
            } else {
                isAknown = true;
                A = i;
            }
            continue;
        }

        if (S[i] >= 2) {
            S[i] -= 2;
            if (isAknown) {
                A = i;
            } else {
                B = i;
            }
        }

        if (!isAknown) {
            A |= (S[i] << bitA++);
        } else if (!isBknown) {
            B |= (S[i] << bitB++);
        }
    }

    return {A, B};
}

//#include "grader.cpp"

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