Submission #320911

#	Time	Username	Problem	Language	Result	Execution time	Memory
320911		shrek12357	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	1 ms	492 KiB

coprobber

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
#include "coprobber.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0); 

const int MAXN = 505;

bool found[MAXN][MAXN];
vector<int> adjList[MAXN];
int cur = 0, par = 0;
int cnt = 0;
int n;
int row = 0, col = 0;

void dfs(int src, int par) {
	found[src][src] = true;
	for (auto i : adjList[src]) {
		if (i == par) {
			continue;
		}
		dfs(i, src);
		for (int j = 0; j < MAXN; j++) {
			found[src][j] |= found[i][j];
		}
	}
}

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]) {
				adjList[i].push_back(j);
				cnt++;
			}
		}
	}
	if (cnt / 2 == N - 1) {
		dfs(0, 0);
		return cur;
	}
	for (int i = 0; i < n; i++) {
		if (A[i][i + 1]) {
			col++;
		}
		else {
			break;
		}
	}
	row = N / col;
	cur = 0;
	return 0;
}

int nextMove(int R) {
	if (cnt == n - 1) {
		if (cur == R) {
			return R;
		}
		for (auto i : adjList[cur]) {
			if (i == par) {
				continue;
			}
			if (found[i][R]) {
				par = cur;
				cur = i;
				return cur;
			}
		}
	}
	int cR = cur / row, cC = cur % col;
	int nR = R / row, nC = R % col;
	if (abs(nR - cR) + abs(nC - cC) == 1) {
		return R;
	}
	if (abs(nR - cR) < 2) {
		if (nC - cC == 1 || nC - cC == -1) {
			return cur;
		}
		if (nC > cC) {
			return cur + col;
		}
		if (nC < cC) {
			return cur - col;
		}
	}
	else {
		if (nR > cR) {
			return cur + 1;
		}
		else {
			return cur - 1;
		}
	}
}

Compilation message (stderr)

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

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