Submission #398824

#	Time	Username	Problem	Language	Result	Execution time	Memory
398824		faresbasbs	Cop and Robber (BOI14_coprobber)	C++14	30 / 100	421 ms	9624 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];

int solve(int cp , int cc , int moves , int tag){
	if(moves > 100){
		return 1000000000;
	}
	if(cp == cc){
		return 0;
	}
	if(dp[cp][cc][moves][tag] != -1){
		return dp[cp][cc][moves][tag];
	}
	int ret = 1000000000 , val;
	if(!tag){
		val = 1+solve(cp,cc,moves+1,1);
		if(val < ret){
			nxt[cp][cc] = cp , ret = val;
		}
		for(auto i : graph[cp]){
			val = 1+solve(i,cc,moves+1,1);
			if(val < ret){
				nxt[cp][cc] = i , ret = val;
			}
		}
	}else{
		ret = 0;
		for(int i : graph[cc]){
			ret = max(ret,1+solve(cp,i,moves+1,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);
			}
		}
	}
	curr = -1;
	for(int i = 0 ; i < n ; i += 1){
		bool ok = 1;
		for(int j = 0 ; j < n ; j += 1){
			if(solve(i,j,0,0) == 1000000000){
				ok = 0;
				break;
			}
		}
		if(ok){
			curr = i;
			break;
		}
	}
	return curr;
}

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

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