Submission #528269

#	Time	Username	Problem	Language	Result	Execution time	Memory
528269		Jeff12345121	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	713 ms	14512 KiB

coprobber

#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;
wow last[nmax][nmax][2];

#ifdef LOCAL
const int MAX_N = 500;
#endif

int dp[nmax][nmax][2],nrAdjacent[nmax][nmax],copPosition;
bool situation[nmax][nmax][2];
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 xcop, int xrobber, int xturn) {
            if (dp[xcop][xrobber][xturn] == 0) {
                dp[xcop][xrobber][xturn] = 1;
                last[xcop][xrobber][xturn] = {cop, robber,turn};
                q.push({xcop,xrobber,xturn});
            }
        };
        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 copPosition = last[copPosition][R][0].cop;///cop where we came from. since this is a 0 it came from 1 so the cop changed.

}

#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);

    nextMove(3);
}
#endif

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:73:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 if (nrAdjacent[cop][k] == g[k].size()) {
      |                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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