oj.uz

답안 #873588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873588 2023-11-15T10:27:38 Z sleepntsheep 경찰관과 강도 (BOI14_coprobber) C++17
0 / 100
 1 ms 4440 KB 
#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][2], deg[MAX_N], at;
bool (*A)[MAX_N];

int start(int N, bool A[MAX_N][MAX_N])
{
    ::N = N, ::A = A;
    memset(G, -1, sizeof G);
    std::queue<std::tuple<int, int, int, int>> q;
    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 (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) deg[i] += A[i][j];

    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]) continue;
                if (!g)
                {
                    if (G[k][v][0] == -1)
                        q.emplace(k, v, 0, G[k][v][!t] = 0);
                }
                else
                {
                    if (++C[k][v][1] == deg[k])
                    {
                        q.emplace(k, v, !t, G[k][v][!t] = 1);
                    }
                }
            }
        }
        else /* was robber */
        {
            for (auto k = 0; k < N; ++k)
            {
                if (!A[v][k]) continue;
                if (!g) 
                {
                    if (++C[u][k][0] == deg[k])
                    {
                        q.emplace(u, k, !t, G[u][k][!t] = 0);
                    }
                }
                else if (G[u][k][!t] == -1)
                {
                    q.emplace(u, k, !t, G[u][k][!t] = 1);
                }
            }
        }
    }

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

int nextMove(int R)
{
    if (!G[at][R][1]) return at;
    for (int j = 0; j < N; ++j)
        if (A[at][j] && !G[j][R][1]) return j;
    return -1;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB the situation repeated
4 Halted 0 ms 0 KB -