oj.uz

Submission #15972

# Submission time Handle Problem Language Result Execution time Memory
15972 2015-08-04T08:41:39 Z gs14004 Cop and Robber (BOI14_coprobber) C++14
0 / 100
 2 ms 428 KB 
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 500;

int indeg[MAX_N][MAX_N][2];

queue<int> qx, qy, qd;
bool vis[500][500][2];
int nxt[500][500];
int pos;

int start(int N, bool A[MAX_N][MAX_N])
{
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (i == j){
				continue;
			}
			for (int k = 0; k < N; k++){
				if (A[i][k]){
					indeg[i][j][0] = 1;
				}
				if (A[j][k]){
					indeg[i][j][1]++;
				}
			}
		}
	}
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			for (int k = 0; k < 2; k++){
				if (indeg[i][j][k] == 0){
					qx.push(i), qy.push(j), qd.push(k);
					vis[i][j][k] = 1;
				}
			}
		}
	}
	while (!qx.empty()){
		int yf = qy.front();
		int df = qd.front();
		qx.pop(), qy.pop(), qd.pop();
		int xf = qx.front();
		if (df == 1){
			for (int i = 0; i < N; i++){
				if (!vis[i][yf][0]){
					indeg[i][yf][0]--;
					if (indeg[i][yf][0] == 0){
						qx.push(i);
						qy.push(yf);
						qd.push(0);
						vis[i][yf][0] = 1;
						nxt[xf][yf] = i;
					}
				}
			}
		}
		else{
			for (int i = 0; i < N; i++){
				if (!vis[xf][i][1]){
					indeg[xf][i][1]--;
					if (indeg[xf][i][1] == 0){
						qx.push(xf);
						qy.push(i);
						qd.push(1);
						vis[xf][i][1] = 1;
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++){
		int fnd = 0;
		for (int j = 0; j < N; j++){
			if (!vis[i][j][0]){
				fnd = 1;
				break;
			}
		}
		if (!fnd) return pos = i;
	}
	return -1;
}

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Incorrect 2 ms 356 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 the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Incorrect 2 ms 428 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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB the situation repeated
4 Halted 0 ms 0 KB -