oj.uz

Submission #398824

# Submission time Handle Problem Language Result Execution time Memory
398824 2021-05-04T20:45:22 Z faresbasbs Cop and Robber (BOI14_coprobber) C++14
30 / 100
 421 ms 9624 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8392 KB Output is correct
2 Correct 4 ms 8392 KB Output is correct
3 Correct 5 ms 8396 KB Output is correct
4 Incorrect 78 ms 9532 KB the situation repeated
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8392 KB Output is correct
2 Correct 5 ms 8392 KB Output is correct
3 Incorrect 109 ms 9624 KB nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8264 KB Output is correct
2 Correct 4 ms 8392 KB Output is correct
3 Correct 5 ms 8392 KB Output is correct
4 Correct 4 ms 8392 KB Output is correct
5 Correct 5 ms 8392 KB Output is correct
6 Correct 4 ms 8392 KB Output is correct
7 Correct 4 ms 8392 KB Output is correct
8 Correct 4 ms 8392 KB Output is correct
9 Correct 6 ms 8392 KB Output is correct
10 Correct 83 ms 8476 KB Output is correct
11 Correct 404 ms 8520 KB Output is correct
12 Correct 10 ms 8392 KB Output is correct
13 Correct 44 ms 8392 KB Output is correct
14 Correct 184 ms 8456 KB Output is correct
15 Correct 26 ms 8536 KB Output is correct
16 Correct 36 ms 8532 KB Output is correct
17 Correct 421 ms 8692 KB Output is correct
18 Correct 20 ms 8404 KB Output is correct
19 Correct 5 ms 8300 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8392 KB Output is correct
2 Correct 4 ms 8392 KB Output is correct
3 Correct 5 ms 8396 KB Output is correct
4 Incorrect 78 ms 9532 KB the situation repeated
5 Halted 0 ms 0 KB -