제출 #1231596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231596		kaiboy	Cop and Robber (BOI14_coprobber)	C++20	100 / 100	286 ms	9720 KiB

coprobber

#include "coprobber.h"
#include <algorithm>
#include <iostream>

const int N = 500;

int pp[N][N], kk[N][N], qu[N * N * 2][3], i;

int start(int n, bool aa[][N]) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			pp[i][j] = -1;
		pp[qu[cnt][0] = i][qu[cnt][1] = i] = i, qu[cnt][2] = 0, cnt++;
	}
	for (int j = 0; j < n; j++) {
		int k = 0;
		for (int j_ = 0; j_ < n; j_++)
			if (aa[j][j_])
				k++;
		for (int i = 0; i < n; i++)
			kk[i][j] = k;
		kk[j][j] = 0, qu[cnt][0] = qu[cnt][1] = j, qu[cnt][2] = 1, cnt++;
	}
	for (int h = 0; h < cnt; h++) {
		int i = qu[h][0], j = qu[h][1], t = qu[h][2];
		if (!t) {
			for (int j_ = 0; j_ < n; j_++)
				if (aa[j_][j] && !--kk[i][j_])
					qu[cnt][0] = i, qu[cnt][1] = j_, qu[cnt][2] = 1, cnt++;
		} else {
			for (int i_ = 0; i_ < n; i_++)
				if ((i_ == i || aa[i_][i]) && pp[i_][j] == -1)
					pp[qu[cnt][0] = i_][qu[cnt][1] = j] = i, qu[cnt][2] = 0, cnt++;
		}
	}
	for (i = 0; i < n; i++) {
		bool yes = true;
		for (int j = 0; j < n; j++)
			if (pp[i][j] == -1) {
				yes = false;
				break;
			}
		if (yes)
			break;
	}
	return i < n ? i : -1;
}

int nextMove(int j) {
	return i = pp[i][j];
}

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