Submission #398816

#	Time	Username	Problem	Language	Result	Execution time	Memory
398816		faresbasbs	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	57 ms	9536 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
int n,curr,dp[101][101][101][2],nxt[101][101];
vector<int> graph[501];

bool solve(int cp , int cc , int moves , int tag){
	if(moves > 100){
		return 0;
	}
	if(cp == cc){
		return 1;
	}
	if(dp[cp][cc][moves][tag] != -1){
		return dp[cp][cc][moves][tag];
	}
	int ret = 0;
	if(!tag){
		if(solve(cp,cc,moves+1,1)){
			nxt[cp][cc] = cp , ret = 1;
		}
		for(auto i : graph[cp]){
			if(solve(i,cc,moves+1,1)){
				nxt[cp][cc] = i , ret = 1;
			}
		}
	}else{
		ret = 1;
		for(int i : graph[cc]){
			if(!solve(cp,i,moves+1,0)){
				ret = 0;
			}
		}
	}
	return dp[cp][cc][moves][tag] = ret;
}

int start(int N , bool grid[MAX_N][MAX_N]){
	memset(dp,-1,sizeof dp);
	n = N;
	for(int i = 0 ; i < n ; i += 1){
		for(int j = 0 ; j < n ; j += 1){
			if(grid[i][j]){
				graph[i].push_back(j);
			}
		}
	}
	for(int i = 0 ; i < n ; i += 1){
		if(!solve(0,i,0,0)){
			return -1;
		}
	}
	return 0;
}

int nextMove(int r){
	return curr = nxt[curr][r];
}

Compilation message (stderr)

coprobber.cpp: In function 'bool solve(int, int, int, int)':
coprobber.cpp:35:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |  return dp[cp][cc][moves][tag] = ret;
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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