oj.uz

Submission #398821

# Submission time Handle Problem Language Result Execution time Memory
398821 2021-05-04T20:42:39 Z faresbasbs Cop and Robber (BOI14_coprobber) C++14
30 / 100
 326 ms 9600 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 4 ms 8392 KB Output is correct
2 Correct 4 ms 8392 KB Output is correct
3 Correct 4 ms 8300 KB Output is correct
4 Incorrect 78 ms 9536 KB the situation repeated
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8392 KB Output is correct
2 Correct 5 ms 8392 KB Output is correct
3 Incorrect 101 ms 9600 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 8392 KB Output is correct
2 Correct 4 ms 8392 KB Output is correct
3 Correct 4 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 5 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 80 ms 8448 KB Output is correct
11 Correct 326 ms 8480 KB Output is correct
12 Correct 10 ms 8404 KB Output is correct
13 Correct 39 ms 8428 KB Output is correct
14 Correct 145 ms 8392 KB Output is correct
15 Correct 23 ms 8520 KB Output is correct
16 Correct 32 ms 8504 KB Output is correct
17 Correct 322 ms 8696 KB Output is correct
18 Correct 18 ms 8392 KB Output is correct
19 Correct 4 ms 8392 KB Output is correct

Subtask #4
0 / 40.0

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