Submission #230088

#	Time	Username	Problem	Language	Result	Execution time	Memory
230088		dolphingarlic	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	507 ms	7648 KiB

coprobber

#include "coprobber.h"
#include <algorithm>
#include <queue>
 
using namespace std;
 
struct Position {
  int a, b, c;
  Position (int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) { }
};
  
 
const int COP = 0, ROBBER = 1;
int LeftToWin[2][MAX_N][MAX_N];
int NextPos[MAX_N][MAX_N];
 
int start(int N, bool A[MAX_N][MAX_N]) {
	for (int r = 0; r < N; r++) {
		int degree = count(A[r], A[r] + N, true);
		for (int c = 0; c < N; c++)
			if (c != r) {
				LeftToWin[COP][c][r] = 1;
				LeftToWin[ROBBER][c][r] = degree;
			}
	}
 
	queue<Position> q;
	for (int i = 0; i < N; i++) {
		q.push(Position(COP, i, i));
		q.push(Position(ROBBER, i, i));
	}
	
	int numProcessed = 0;
	while (!q.empty()) {
		int t, c, r;
      Position tmp = q.front();
      t = tmp.a; c = tmp.b; r = tmp.c;
		q.pop();
		numProcessed++;
		if (t == COP) {
			for (int n = 0; n < N; n++)
				if (A[r][n] && LeftToWin[ROBBER][c][n]) {
					LeftToWin[ROBBER][c][n]--;
					if (LeftToWin[ROBBER][c][n] == 0)
						q.push(Position(ROBBER, c, n));
				}
		} else if (t == ROBBER) {
			for (int n = 0; n < N; n++)
				if ((c == n || A[c][n]) && LeftToWin[COP][n][r]) {
					LeftToWin[COP][n][r] = 0;
					q.push(Position(COP, n, r));
					NextPos[n][r] = c;
				}
		}
	}
	
	return numProcessed == 2*N*N ? 0 : -1;
}
 
int cop = 0;
 
int nextMove(int robber) {
	cop = NextPos[cop][robber];
	return cop;
}

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