제출 #81205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81205		antimirage	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	782 ms	39760 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
//#include "grader.cpp"

using namespace std;

const int M = 505;

int n, used[2][M][M], win[2][M][M], ar[M][M], to[2][M][M], ind1, ind2;

void dfs (int type, int x, int y)
{
	used[type][x][y] = 1;
	
	for (int i = 1; i <= n; i++)
	{
		if (type == 0 && ar[x][i] == 0 && i != x) continue;
		if (type == 1 && ar[y][i] == 0) continue;
		
		if (type == 0)
		{
			if (win[1][i][y] == 0)
				win[0][x][y] = 1, to[0][x][y] = i;
		}
		else
		{
			if (win[0][x][i] == 0)
				win[1][x][y] = 1, to[1][x][y] = i;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (type == 0 && ar[x][i] == 0 && i != x) continue;
		if (type == 1 && ar[y][i] == 0) continue;
		
		if (to[type][x][y] == 0) to[type][x][y] = i;
		
		if (type == 0)
		{
			if ( !used[1][i][y] )
				dfs(1, i, y);
				
			if (win[1][i][y] == 0)
				win[0][x][y] = 1, to[0][x][y] = i;
		}
		else
		{
			if ( !used[0][x][i] )
				dfs(0, x, i);
				
			if (win[0][x][i] == 0)
				win[1][x][y] = 1, to[1][x][y] = i;
			if (used[0][x][i] == 1 && win[0][x][i] == -1)
				win[1][x][y] = 1, to[1][x][y] = i;
		}
	}
	if (win[type][x][y] == -1)
		win[type][x][y] = 0;
		
	used[type][x][y] = 2;
}
int start(int N, bool A[MAX_N][MAX_N])
{
	memset(win, -1, sizeof(win) );
	n = N;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			ar[i][j] = A[i - 1][j - 1];
			
		used[1][i][i] = 2;
		win[1][i][i] = 0;
			
		for (int j = 1; j <= n; j++)
		{
			if ( ar[i][j] || i == j )
				win[0][i][j] = 1, used[0][i][j] = 2, to[0][i][j] = j;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (used[0][i][j] == 0) dfs(0, i, j);
			if (used[1][i][j] == 0) dfs(1, i, j);
		}
	}
	for(int i = 1; i <= n; i++)
	{
		bool fl = 1;
		for (int j = 1; j <= n; j++)
		{
			if (win[0][i][j] == 0) fl = 0;
		}
		if (fl)
			ind1 = i;
	}
	ind1--;
	return ind1;	
}

int nextMove(int R)
{
	ind2 = R;
    return ind1 = to[0][ind1 + 1][ind2 + 1] - 1;
}
/**
4
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
1
0 0 0 0 1
2 0 0 0 2
1 0 0 0 1
1 0 0 0 1
**/

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