Submission #873607

#	Time	Username	Problem	Language	Result	Execution time	Memory
873607		sleepntsheep	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	853 ms	10016 KiB

coprobber

#include "coprobber.h"
#include <tuple>
#include <array>
#include <queue>
#include <string.h>

int N, G[MAX_N][MAX_N][2], C[MAX_N][MAX_N], D[MAX_N][MAX_N], deg[MAX_N], at;
bool (*A)[MAX_N];

int start(int N, bool A[MAX_N][MAX_N])
{
    ::N = N, ::A = A;
    std::queue<std::tuple<int, int, int, int>> q;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) deg[i] += A[i][j], G[i][j][0] = G[i][j][1] = 1;
    for (int i = 0; i < N; ++i) G[i][i][0] = G[i][i][1] = 0, q.emplace(i, i, 0, 0), q.emplace(i, i, 1, 0);

    for (; q.size(); )
    {
        auto [u, v, t, g] = q.front();
        q.pop();
        if (t) /* robber, was cop */
        {
            for (auto k = 0; k < N; ++k)
            {
                if (!A[u][k] && k != u) continue;
                if (G[k][v][!t])
                    q.emplace(k, v, !t, G[k][v][!t] = 0), D[k][v] = u;
            }
        }
        else /* was robber */
        {
            for (auto k = 0; k < N; ++k)
            {
                if (!A[v][k]) continue;
                if (++C[u][k] == deg[k])
                    q.emplace(u, k, !t, G[u][k][!t] = 0);
            }
        }
    }

    for (int win = 0, i = 0; i < N; ++i)
        for (int j = win = 0; j < N; ++j) if ((win += !G[i][j][0]) == N) return at = i;
    return -1;
}

int nextMove(int R)
{
    return at = D[at][R];
}

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