제출 #1146790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146790		BlockOG	게임 (IOI14_game)	C++20	42 / 100	1095 ms	4864 KiB

game

// mrrrow mnyaa ;3c
// go play vivid/stasis! it's a really awesome free game on steam

int links[1502][1502][2];
int num_edges[1502];
int min_num_edges;
bool used[1502];
int n, call_num;

void initialize(int N) {
    n = N;
    call_num = 0;
    min_num_edges = n - 1;
    for (int i = 1; i <= n; i++) {
        links[i][0][1] = 1;
        for (int j = 0; j < n; j++) {
            links[i][j + 1][0] = j;
            links[i][j + 1][1] = j + 2;
        }
        links[i][n + 1][1] = -1;
        num_edges[i] = n - 1;
    }
}

bool dfs(int i, int j, int mi, int ma) {
    used[i] = true;

    for (int it = links[i][0][1]; it <= ma && links[i][it][1] != -1; it = links[i][it][1])
        if (it >= mi && it == j || !used[it] && dfs(it, j, mi, ma)) return true;

    return false;
}

int hasEdge(int u, int v) {
    call_num++;
    u++, v++;

    int up = links[u][v][0], un = links[u][v][1];
    int vp = links[v][u][0], vn = links[v][u][1];

    links[u][up][1] = un;
    links[u][un][0] = up;

    links[v][vp][1] = vn;
    links[v][vn][0] = vp;

    num_edges[u]--;
    num_edges[v]--;

    int min_of = num_edges[u] < num_edges[v] ? num_edges[u] : num_edges[v];

    if (call_num < n - 1) {
        min_num_edges = min_of < min_num_edges ? min_of : min_num_edges;
        return false;
    }
    if (min_num_edges >= n / 2) {
        min_num_edges = min_of < min_num_edges ? min_of : min_num_edges;
        return false;
    }

    for (int i = 1; i <= n; i++) used[i] = false;

    int r = 0xffff;
    while (u & r > 0 && v | ~r < n) {
        if (dfs(u, v, u & r, v & ~r)) {
            min_num_edges = min_of < min_num_edges ? min_of : min_num_edges;
            return false;
        }
        r <<= 1;
    }

    if (!dfs(u, v, 0, n)) {
        links[u][up][1] = v;
        links[u][un][0] = v;

        links[v][vp][1] = u;
        links[v][vn][0] = u;

        num_edges[u]++;
        num_edges[v]++;
        min_of++;

        min_num_edges = min_of < min_num_edges ? min_of : min_num_edges;

        return true;
    } else {
        min_num_edges = min_of < min_num_edges ? min_of : min_num_edges;
        return false;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58