제출 #1251694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251694		fv3	Migrations (IOI25_migrations)	C++20	0 / 100	468 ms	1224 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 (ai == i) {
            Aunknown = false;
            return 2;
        } else if (bi == i) {
            Bunknown = false;
            return 3;
        }

        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 (S[i] == 2) {
            isAunknown = false;
            A = i;
        } else if (S[i] == 3) {
            isBunknown = false;
            B = i;
        }

        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: 0 / 30
• Subtask 2: 0 / 70