Submission #780652

#	Time	Username	Problem	Language	Result	Execution time	Memory
780652		rxlfd314	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	473 ms	7088 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
using ari3 = array<int, 3>;

int nxt[500][500], cur = -1;

int start(int N, bool A[500][500]) {
	queue<ari3> qu;
	bool cw[N][N][2] = {};
	int deg[N][N] = {};
	for (int i = 0; i < N; i++) {
		cw[i][i][0] = true;
		qu.push({i, i, 0});
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				deg[i][j] += A[j][k];
			}
		}
	}
	
	while (qu.size()) {
		auto [i, j, m] = qu.front();
		qu.pop();
		for (int k = 0; k < N; k++) {
			if (m && A[j][k]) {
				if (cw[i][k][0]) continue;
				if (!--deg[i][k]) {
					cw[i][k][0] = true;
					qu.push({i, k, 0});
				}
			} else if (!m && (A[i][k] || i == k)) {
				if (cw[k][j][1]) continue;
				cw[k][j][1] = true;
				qu.push({k, j, 1});
				nxt[k][j] = i;
			}
		}
	}
	
	for (int i = 0; i < N; i++) {
		bool can = true;
		for (int j = 0; j < N; j++) {
			can &= cw[i][j][1];
		}
		cur = can ? i : cur;
	}
	return cur;
} 

int nextMove(int r) {
	return cur = nxt[cur][r];
}

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