oj.uz

Submission #26190

# Submission time Handle Problem Language Result Execution time Memory
26190 2017-06-28T09:01:37 Z chpipis Cop and Robber (BOI14_coprobber) C++11
0 / 100
 266 ms 22424 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Incorrect 266 ms 22336 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Incorrect 3 ms 1408 KB Cop can catch the robber, but start() returned -1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Incorrect 3 ms 1408 KB Cop can catch the robber, but start() returned -1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 3 ms 1280 KB Output is correct
4 Incorrect 257 ms 22424 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -