Submission #296872

#	Time	Username	Problem	Language	Result	Execution time	Memory
296872		luciocf	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	857 ms	7544 KiB

coprobber

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

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 510;

int n;
int at;

bool liga[maxn][maxn];
int grau[maxn][maxn];

int pai[maxn][maxn];

bool win[2][maxn][maxn];

int start(int N, bool A[MAX_N][MAX_N])
{
	int n = N;

    queue<pair<pii, int>> fila;

    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
    		liga[i][j] = A[i][j];

    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
    		for (int k = 0; k < n; k++)
    			grau[i][j] += liga[j][k];

    for (int i = 0; i < n; i++)
    {
    	win[0][i][i] = win[1][i][i] = 1;

    	fila.push({{i, i}, 0});
    	fila.push({{i, i}, 1});
    }

   	while (!fila.empty())
   	{
   		int a = fila.front().ff.ff, b = fila.front().ff.ss, q = fila.front().ss;
   		fila.pop();

   		for (int i = 0; i < n; i++)
   		{
   			if (q == 0) // Cop
   			{
   				if ((liga[a][i] || a == i) && !win[1][i][b])
   				{
   					pai[i][b] = a;

   					win[1][i][b] = 1;
   					fila.push({{i, b}, 1});
   				}
   			}
   			else // Robber
   			{

   				if (liga[b][i] && !win[0][a][i] && --grau[a][i] <= 0)
   				{
   					win[0][a][i] = 1;
   					fila.push({{a, i}, 0});
   				}
   			}
   		}
   	}

   	for (int i = 0; i < n; i++)
   	{
   		bool ok = 1;

   		for (int j = 0; j < n; j++)
   			if (!win[0][i][j])
   				ok = 0;

   		if (ok) return at = i;
   	}

   	return -1;
}

int nextMove(int R)
{
	return at = pai[at][R];
}

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