Submission #528237

# Submission time Handle Problem Language Result Execution time Memory
528237 2022-02-19T18:08:42 Z Jeff12345121 Cop and Robber (BOI14_coprobber) C++14
0 / 100
1 ms 328 KB
#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#include "coprobber.h"
#endif

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#endif

struct wow {
    int cop,robber,turn;
};
vector<vector<int>> g;
const int nmax = 505;

#ifdef LOCAL
const int MAX_N = 500;
#endif

int dp[nmax][nmax][2],nrAdjacent[nmax][nmax],copPosition,situation[nmax];
int start(int n, bool a[MAX_N][MAX_N]) {
    queue<wow> q;
    g.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 1) {
                g[i].push_back(j);
            }
        }
    }


    ///dp[i][j][turn], turn = 0 -> cops turn, 1->robber's turn
    ///dp is 1 if from this position cop can catch robber, 0 otherwise
    ///if it's 1 and turn = 0, then move[i][j] should contain a possible move for the cop
    ///that he can make so he can get to the robber.

    for (int i = 0; i < n; i++) {
        dp[i][i][0] = dp[i][i][1] = 1;
        q.push({i,i,0});
        q.push({i,i,1});
    }
    ///queue just contains values that have been turned to 1
    while(!q.empty()) {
        int cop = q.front().cop;
        int robber = q.front().robber;
        int turn = q.front().turn;
        q.pop();

        auto change = [&](int cop, int robber, int turn) {
            if (dp[cop][robber][turn] == 0) {
                dp[cop][robber][turn] = 1;
            }
            q.push({cop,robber,turn});
        };
        if (turn == 1) { // robber's turn, this leads to the samae position in 0, as well as all neighbours of the cop in 0.
            for (auto k : g[cop]) {
                change(k,robber,0);
            }
            change(cop,robber,0);///cop can wait and get lead to this situation.
        } else {
            ///any neighbours 1's need to have all of their robber neighbours taken
            ///we take a robber move from a certain neighbour to get here
            for (auto k : g[robber]) {
                nrAdjacent[cop][k]++;///nr of adjacent cop move nodes that are 1 next to this robber move
                if (nrAdjacent[cop][k] == g[k].size()) {
                    change(cop, k, 1);///this robber turn position is taken
                }
            }
        }
    }

    ///we want to find a corner where all dp[A][x][0] = 1
    for (int i = 0; i < n; i++) {
        bool any0 = false;
        for (int j = 0; j < n; j++) {
            if (dp[i][j][0] == 0) {
                any0 = true;
                break;
            }
        }
        if (!any0) {
            copPosition = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    return -1;
    situation[copPosition]++;
    for (auto nextCop : g[copPosition]) {
        if (dp[nextCop][R][1] == 1 && situation[nextCop] == 0) { /// it will be the robber's turn after this move
            return nextCop;
        }
    }
   // if (dp[copPosition] == 1) {
        
   // }
    return -1;
}

#ifdef LOCAL
bool a[MAX_N][MAX_N];

int main() {
    int n;
    in >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            in >> a[i][j];
        }
    }

    start(n , a);
}
#endif

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:69:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 if (nrAdjacent[cop][k] == g[k].size()) {
      |                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
2 Halted 0 ms 0 KB -