제출 #1251739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251739		fv3	이주 (IOI25_migrations)	C++20	30 / 100	694 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 Aunknown = true;
bool Bunknown = true;

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 (!(Aunknown && Abit < 14) && !(Bunknown && Bbit < 14)) {
            if (ai == i) {
                return 1;
            } else if (bi == i) {
                return 2;
            }

            return 0;
        }

        if (ai == i) {
            if (Aunknown && Abit < 14) {
                Aunknown = false;
                return 4;
            } else {
                return (2 | ((bi & (1 << Bbit++)) ? 1 : 0));
            }
        } else if (bi == i) {
            if (Bunknown && Bbit < 14) {
                Bunknown = false;
                return 4;
            } else {
                return (2 | ((ai & (1 << Abit++)) ? 1 : 0));
            }
        }

        if (Aunknown && Abit < 14) {
            return ((ai & (1 << Abit++)) ? 1 : 0);
        } else if (Bunknown && Bbit < 14) {
            return ((bi & (1 << Bbit++)) ? 1 : 0);
        }
    }

    return 0;
}

pair<int, int> longest_path(vector<int> S) {
    int A = 0, B = 0;
    bool isAunknown = true;
    bool isBunknown = true;

    int bitA = 0;
    int bitB = 0;

    for (int i = N - 28; i < N; i++) {
        if (!(isAunknown && bitA < 14) && !(isBunknown && bitB < 14)) {
            if (S[i] == 1) {
                A = i;
            } else if (S[i] == 2) {
                B = i;
            }
            continue;
        }

        if (S[i] == 4) {
            if (isBunknown && bitB < 14) {
                isBunknown = false;
                B = i;
            } else {
                isAunknown = false;
                A = i;
            }

            continue;
        }

        if (S[i] >= 2) {
            S[i] -= 2;
            if (!(isAunknown && bitA < 14)) {
                A = i;
                if (isBunknown && bitB < 14) {
                    B |= (S[i] << bitB++);
                }
            } else {
                B = i;
                if (isAunknown && bitA < 14) {
                    A |= (S[i] << bitA++);
                } 
            }
            continue;
        }

        if (isAunknown && bitA < 14) {
            A |= (S[i] << bitA++);
        } else if (isBunknown && bitB < 14) {
            B |= (S[i] << bitB++);
        }
    }

    return {A, B};
}

//#include "grader.cpp"

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