Submission #5968

#	Time	Username	Problem	Language	Result	Execution time	Memory
5968		ainta	Cop and Robber (BOI14_coprobber)	C++98	100 / 100	934 ms	7684 KiB

coprobber

#include "coprobber.h"

int P[MAX_N][MAX_N], Q[MAX_N][MAX_N];
int E[MAX_N][MAX_N];
int C2[MAX_N][MAX_N], n;
int Deg[MAX_N];
int Q1[MAX_N*MAX_N], Q2[MAX_N*MAX_N], t1, t2, h1, h2;
int node;

void UDT1(int x, int y)
{
	int i;
	for (i = 0; i < n; i++){
		if (E[y][i]){
			C2[x][i]++;
			if (C2[x][i] == Deg[i]){
				Q[x][i] = P[x][y];
				Q2[++t2] = (x << 9) + i;
			}
		}
	}
}

void UDT2(int x, int y)
{
	int i;
	for (i = 0; i < n; i++){
		if (E[x][i] && !P[i][y]){
			Q1[++t1] = (i << 9) + y;
			P[i][y] = Q[x][y] + 1;
		}
	}
	if (!P[x][y]){
		Q1[++t1] = (x << 9) + y;
		P[x][y] = Q[x][y] + 1;
	}
}

int start(int N, bool A[MAX_N][MAX_N])
{
	n = N;
	int i, j, k;
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			E[i][j] = A[i][j];
			if (E[i][j])Deg[i]++;
		}
	}
	for (i = 0; i < n; i++){
		P[i][i] = 1;
		UDT1(i, i);
		for (j = 0; j < n; j++){
			if (A[i][j]){
				P[i][j] = 1;
				UDT1(i, j);
			}
		}
	}
	while (h2<t2){
		while (h2<t2){
			++h2;
			UDT2(Q2[h2] >> 9, Q2[h2] & 511);
		}
		while (h1<t1){
			++h1;
			UDT1(Q1[h1] >> 9, Q1[h1] & 511);
		}
	}
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			if (!P[i][j])break;
		}
		if (j == n)break;
	}
	if (i == n)return -1;
	node = i;
	return i;
}

int nextMove(int R)
{
	if (E[node][R] || node == R){
		return R;
	}
	int i, M = 9999999, x;
	for (i = 0; i < n; i++){
		if ((E[node][i] || i == node) && Q[i][R] && M > Q[i][R]){
			M = Q[i][R];
			x = i;
		}
	}
	node = x;
	return x;
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:42:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:92:7: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  node = x;
  ~~~~~^~~

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