Submission #26190

#	Time	Username	Problem	Language	Result	Execution time	Memory
26190		chpipis	Cop and Robber (BOI14_coprobber)	C++11	0 / 100	266 ms	22424 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

bool mat[MAX_N + 5][MAX_N + 5];
bool visit[MAX_N + 5][MAX_N + 5][2];
bool memo[MAX_N + 5][MAX_N + 5][2];
int n;

bool dp(int o, int r, int f) {
    if (o == r)
        return true;
    if (visit[o][r][f])
        return memo[o][r][f];
    visit[o][r][f] = true;
    if (f == 0) {
        bool win = false;
        for (int i = 0; i < n; i++)
            if (i == o || mat[o][i])
                win |= dp(i, r, f ^ 1);
        memo[o][r][f] = win;
    } else {
        bool win = true;
        for (int i = 0; i < n; i++)
            if (mat[r][i])
                win &= dp(o, i, f ^ 1);
        memo[o][r][f] = win;
    }
    return memo[o][r][f];
}

int last_pos;

int start(int N, bool A[MAX_N][MAX_N]) {
    n = N;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mat[i][j] = A[i][j];
    memset(visit, false, sizeof visit);
    memset(memo, false, sizeof memo);
    int pos = -1;
    for (int i = 0; i < n; i++) {
        bool win = true;
        for (int j = 0; j < n; j++)
            win &= dp(i, j, 0);
        if (win) pos = i;
    }
    last_pos = pos;
    return pos;
}

int nextMove(int R) {
    for (int i = 0; i < n; i++)
        if ((last_pos == i || mat[last_pos][i]) && dp(i, R, 1)) {
            return last_pos = i;
        }
    return -1;
}

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