Submission #544611

#	Time	Username	Problem	Language	Result	Execution time	Memory
544611		rainboy	Cop and Robber (BOI14_coprobber)	C++98	100 / 100	693 ms	5696 KiB

coprobber

#include <iostream>

using namespace std;

#define MAX_N	500

// modify the following functions
// you can define global variables and functions

int qu[MAX_N * MAX_N * 2], dd[MAX_N][MAX_N], nxt[MAX_N][MAX_N];
int i_;

int start(int N, bool A[MAX_N][MAX_N]) {
	int i, j, k;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			nxt[i][j] = -1;
	int head = 0, cnt = 0;
	for (j = 0; j < N; j++) {
		int d = 0;
		for (k = 0; k < N; k++)
			if (A[j][k])
				d++;
		for (i = 0; i < N; i++)
			if (i == j)
				qu[head + cnt++] = (i * N + j) * 2 + 1;
			else
				dd[i][j] = d;
	}
	while (cnt) {
		int ijt = qu[cnt--, head++], i = ijt / 2 / N, j = ijt / 2 % N, t = ijt % 2;
		if (t == 1) {
			for (k = 0; k < N; k++)
				if ((k == i || A[k][i]) && nxt[k][j] == -1)
					nxt[k][j] = i, qu[head + cnt++] = (k * N + j) * 2 + 0;
		} else {
			for (k = 0; k < N; k++)
				if (A[k][j] && --dd[i][k] == 0)
					qu[head + cnt++] = (i * N + k) * 2 + 1;
		}
	}
	return head == N * N * 2 ? 0 : -1;
}

int nextMove(int R) {
	return (i_ = nxt[i_][R]);
}

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