Submission #202876

#	Time	Username	Problem	Language	Result	Execution time	Memory
202876		faremy	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	670 ms	5112 KiB

coprobber

#include "coprobber.h"
#include <vector>


struct State
{
	State(int c, int r, int p) : posCop(c), posRob(r), player(p) {}
	int posCop, posRob, player;
};

const int MAXN = 500;

int nodeDeg[MAXN];
int degree[MAXN][MAXN][2];
std::vector<State> rm;

bool copWin[MAXN][MAXN][2];
int go[MAXN][MAXN];
int posCop = -1;


void process(int cop, int robber, int player, int from)
{
	if (!copWin[cop][robber][player])
	{
		if (player == 0)
			go[cop][robber] = from;
		copWin[cop][robber][player] = true;
		rm.emplace_back(cop, robber, player);
	}
}

int start(int N, bool A[MAX_N][MAX_N])
{
	for (int iNode = 0; iNode < N; iNode++)
		for (int jNode = 0; jNode < N; jNode++)
			nodeDeg[iNode] += A[iNode][jNode];

	for (int iCop = 0; iCop < N; iCop++)
		for (int iRobber = 0; iRobber < N; iRobber++)
		{
			go[iCop][iRobber] = -1;
			degree[iCop][iRobber][0] = nodeDeg[iCop] + 1;
			degree[iCop][iRobber][1] = nodeDeg[iRobber];
		}

	for (int iNode = 0; iNode < N; iNode++)
		process(iNode, iNode, 1, -1);
	while (!rm.empty())
	{
		int cop = rm.back().posCop;
		int robber = rm.back().posRob;
		int player = rm.back().player;
		rm.pop_back();

		if (player == 1)
			process(cop, robber, 0, cop);

		for (int iEsc = 0; iEsc < N; iEsc++)
		{
			if (player == 1 && A[cop][iEsc])
				process(iEsc, robber, 0, cop);
			if (player == 0 && A[robber][iEsc])
			{
				degree[cop][iEsc][1]--;
				if (degree[cop][iEsc][1] == 0)
					process(cop, iEsc, 1, -1);
			}
		}
	}

	for (int iCop = 0; iCop < N; iCop++)
	{
		bool isWinner = true;
		for (int iRobber = 0; iRobber < N; iRobber++)
			isWinner &= copWin[iCop][iRobber][0];
		if (isWinner)
		{
			posCop = iCop;
			return iCop;
		}
	}

	return -1;
}

int nextMove(int R)
{
	int next = go[posCop][R];
	posCop = next;
    return next;
}

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