Submission #199151

#	Time	Username	Problem	Language	Result	Execution time	Memory
199151		dolphingarlic	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	473 ms	70296 KiB

coprobber

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

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

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

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

void add_edge(int a, int b, int c, int 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 (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        states.push_back(State(i, j, 0));
        states.push_back(State(i, j, 1));
    }

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (i == j) continue;
        add_edge(i, j, i, j, 1);
        for (int 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 (State i : states) if (!deg_in[i]) {
        q.push(i);
        win[i] = 1;
    }
    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 (int i = 0; i < N; i++) {
        bool guarantee = true;
        for (int j = 0; j < N; j++) guarantee &= win[State(i, j, 1)];
        if (guarantee) {
            here = {i, -1, 1};
            return i;
        }
    }
    return -1;
}

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

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