Submission #135841

#	Time	Username	Problem	Language	Result	Execution time	Memory
135841		tdwn	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	880 ms	10708 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 510;

class game_state {
public:
	int c, r, turn;
};

bool winning[maxn][maxn][2];
bool visited[maxn][maxn][2];
int g_cnt[maxn][maxn][2];

int g[maxn];

int nxt_move[maxn][maxn][2];
int position;

int start(int N, bool A[MAX_N][MAX_N])
{
	queue<game_state>q;
	for(int i=0;i<N;i++) {
		winning[i][i][0] = winning[i][i][1] = true;
		visited[i][i][0] = winning[i][i][1] = true;
		q.push({i, i, 0});
		q.push({i, i, 1});
	}

	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			if(A[i][j]) g[i]++;
		}
	}

	for(int c=0;c<N;c++) {
		for(int r=0;r<N;r++) {
			g_cnt[c][r][1] = g[r];
		}
	}

	// Doing everything backwards
	while(!q.empty()) {
		int cop = q.front().c;
		int robber = q.front().r;
		int turn = q.front().turn;
		q.pop();

		// From which states is this state reachable

		/*cout<<"Winning state is: "<<cop<<" "<<robber<<" with turn on ";
		if(turn == 0) cout<<"police\n";
		else cout<<"robber\n";*/

		if(turn == 1) {
			for(int i=0;i<N;i++) {
				if(i == cop || A[i][cop]) {
					if(!visited[i][robber][0]) {
						winning[i][robber][0] = visited[i][robber][0] = true;

						nxt_move[i][robber][0] = cop;

						q.push({i, robber, 0});
					}
				}
			}
		}
		else {
			// robber's turn, this is winning state, in order to make other state winning state
			// we should make sure each move to that state is winning move

			for(int i=0;i<N;i++) {
				if(A[robber][i]) {
					g_cnt[cop][i][1]--;

					if(g_cnt[cop][i][1] == 0 && !visited[cop][i][1]) {
						visited[cop][i][1] = winning[cop][i][1] = true;

						nxt_move[cop][i][1] = robber;
						q.push({cop, i, 1});
					} 
				}
			}
		}
	}

	for(int cop=0;cop<N;cop++) {
		int br = 0;
		for(int r=0;r<N;r++) {
			if(winning[cop][r][0]) br++;
		}
		if(br == N) {
			position = cop;
			return cop;
		}
	}
	return -1;
}

int nextMove(int R)
{
    return position = nxt_move[position][R][0];
}

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