oj.uz

Submission #5965

# Submission time Handle Problem Language Result Execution time Memory
5965 2014-06-07T05:53:09 Z ainta Cop and Robber (BOI14_coprobber) C++
0 / 100
 2 ms 512 KB 
#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] && P[i][R] && M > P[i][R]){
			M = P[i][R];
			x = i;
		}
	}
	return x;
}

Compilation message

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:85:22: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int i, M = 9999999, x;
                      ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 412 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 412 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 512 KB the situation repeated
4 Halted 0 ms 0 KB -