Submission #250190

#	Time	Username	Problem	Language	Result	Execution time	Memory
250190		Kevin_Zhang_TW	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	3094 ms	4984 KiB

coprobber

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

using namespace std;
#define pb emplace_back
#define MAX_N 500
#define tm asdfasdfoi
const int inf = 1e9;
// modify the following functions
// you can define global variables and functions
int now, n;
vector<int> edge[MAX_N];
int F[MAX_N][MAX_N];
int con[MAX_N][MAX_N], win[MAX_N][MAX_N], lose[MAX_N][MAX_N];
int tm[MAX_N][MAX_N];
int lst, CT;
bool check(int a, int b) {
	if (a == b) return true;
	for (int u : edge[b]) {
		if (!con[a][u]) return false;
	}
	++CT;
	return true;
}
bool ins[MAX_N][MAX_N];
int dfs(int i, int j) {
	if (~win[i][j]) return win[i][j];
	ins[i][j] = true;
	//win[i][j] = false;
	bool ns = false;
	for (int u : edge[j]) {
		bool die = false;
		for (int k : edge[i]) {
			if (ins[k][u]) {
				ns = true;
				continue;
			}
			if (dfs(k, u)) die = true;
		}
		if (ins[i][u]) ns = true;
		else die |= dfs(i, u);
		if (!die) {
			if (!ns) win[i][j] = false;
			ins[i][j] = false;
			return false;
		}
	}
	tm[i][j] = ++CT;
	ins[i][j] = false;
	return win[i][j] = true;
}
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])
				con[i][j] = true, edge[i].pb(j);
		con[i][i] = true;
	}
	for (int i = 0;i < n;++i)
		for (int j = 0;j < n;++j) {
			if (win[i][j] = check(i, j))
				tm[i][j] = ++CT;
			else win[i][j] = -1;
		}

	for (int i = 0;i < n;++i)
		for (int j = 0;j < n;++j)
			if (win[i][j] == -1) 
				dfs(i, j);
	for (int i = 0;i < n;++i) {
		bool allwin = true;
		for (int j = 0;j < n;++j)
			if (!win[i][j]) {
				allwin = false;
				break;
			}
		if (allwin) {
			//assert(i == 0);
			return now = i;
		}
	}
	return -1;
}
int nextMove(int R) {
	if (now == R || con[now][R]) return R;
	for (int u : edge[now]) 
		if (win[u][R] && tm[u][R] < lst)
			return lst = tm[u][R], now = u;
	lst = tm[now][R];
	return now;
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:61:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    if (win[i][j] = check(i, j))
        ~~~~~~~~~~^~~~~~~~~~~~~

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