Submission #105955

#	Time	Username	Problem	Language	Result	Execution time	Memory
105955		luciocf	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	47 ms	2812 KiB

coprobber

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

#define ff first
#define ss second

using namespace std;

const int maxn = 510;

typedef pair<int, int> pii;

int n, U=0;

// ------ TREE STUFF -------
int dist[maxn][maxn];

bool isTree;

vector<int> grafo[maxn];
// -------------------------

// ------ GRID STUFF -------
int ind[maxn][maxn];

bool moveDown, mark[maxn][maxn];

pii pos[maxn];
// -------------------------


bool checkTree(void)
{
	int deg = 0;
	for (int i = 0; i < n; i++)
		deg += (int)grafo[i].size();

	return (deg == 2*(n-1));
}

void bfs(int s)
{
	queue<int> fila;

	dist[s][s] = 0; fila.push(s);

	while (!fila.empty())
	{
		int u = fila.front();
		fila.pop();

		for (auto v: grafo[u])
		{
			if (dist[s][v] != -1) continue;

			dist[s][v] = dist[s][u]+1;
			fila.push(v);
		}
	}
}

int moveTree(int R)
{
	for (auto v: grafo[U])
    {
    	if (dist[v][R] == dist[U][R]-1)
    	{
    		U = v;
    		return v;
    	}
    }
}

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

    for (int i = 0; i < n; i++)
    	for (int j = 0; j < n; j++)
    		if (A[i][j])
    			grafo[i].push_back(j);

    isTree = checkTree();

    if (isTree)
    {
    	memset(dist, -1, sizeof dist);
    	for (int i = 0; i < n; i++)
    		bfs(i);

    	return 0;
    }

    int x = 0, y = 0;
    pos[0] = {x, y}, ind[x][y] = 0;

    for (int i = 1; i < n; i++)
    {
    	if (!A[i][i-1]) y++, x = 0;
    	else x++;

    	pos[i] = {x, y}, ind[x][y] = i;
    }

    return 0;
}

int nextMove(int R)
{
    if (isTree) return moveTree(R);

    int d;

    if (abs(pos[U].ff-pos[R].ff)+abs(pos[U].ss-pos[R].ss) == 2 && !mark[U][R])
    {
    	moveDown = 0;
    	d = U;
    }
    else if ((pos[U].ff == pos[R].ff || moveDown) && !mark[ind[pos[U].ff][pos[U].ss+1]][R])
    {
    	moveDown = 0;
    	d = ind[pos[U].ff][pos[U].ss+1];
    }
    else
    {
    	if (pos[U].ff+1 == pos[R].ff || pos[U].ff-1 == pos[R].ff) moveDown = 1;

    	if (pos[U].ff < pos[R].ff) d = ind[pos[U].ff+1][pos[U].ss];
    	d = ind[pos[U].ff-1][pos[U].ss];
    }

    mark[d][R] = 1, U = d;
    return d;
}

Compilation message (stderr)

coprobber.cpp: In function 'int moveTree(int)':
coprobber.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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