제출 #199159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199159		dolphingarlic	경찰관과 강도 (BOI14_coprobber)	C++14	0 / 100	317 ms	72184 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

struct State {
    short cop, robber;
    bool turn;  // 1 = cop

    State(short c = -1, short r = -1, bool t = -1) : cop(c), robber(r), turn(t) {}
    operator short() const { return 2 * (MAX_N * cop + robber) + turn; }
};

vector<State> graph[3 * MAX_N * MAX_N];
bool win[3 * MAX_N * MAX_N];
short deg_in[3 * MAX_N * MAX_N];
State here, nxt[3 * MAX_N * MAX_N], states[3 * MAX_N * MAX_N];

void add_edge(short a, short b, short c, short d, bool cop) {
    graph[State(c, d, !cop)].push_back(State(a, b, cop));
    deg_in[State(a, b, cop)]++;
}

int start(int N, bool A[MAX_N][MAX_N]) {
    for (short i = 0; i < N; i++) for (short j = 0; j < N; j++) {
        if (i == j) continue;
        add_edge(i, j, i, j, 1);
        for (short k = 0; k < N; k++) if (A[i][k]) {
            add_edge(i, j, k, j, 1);
            add_edge(j, i, j, k, 0);
        }
    }

    queue<State> q; // Reverse BFS
    for (short i = 0; i < N; i++) for (short j = 0; j < N; j++) for (short k = 0; k < 2; k++) {
        if (!deg_in[State(i, j, k)]) {
            q.push(State(i, j, k));
            win[State(i, j, k)] = true;
        }
    }
    while (q.size()) {
        State curr = q.front();
        q.pop();
        for (State i : graph[curr]) {
            deg_in[i]--;
            if (!win[i] && (i.turn || !deg_in[i])) {
                nxt[i] = curr;
                win[i] = true;
                q.push(i);
            }
        }
    }

    for (short i = 0; i < N; i++) {
        bool guarantee = true;
        for (short j = 0; j < N; j++) guarantee &= win[State(i, j, 1)];
        if (guarantee) {
            here = {i, i, 1};
            return (int)i;
        }
    }
    return -1;
}

int nextMove(int R) {
    here.robber = R;
    here.turn = 1;
    here = nxt[here];
    return (int)here.cop;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40