oj.uz

Submission #398820

# Submission time Handle Problem Language Result Execution time Memory
398820 2021-05-04T20:41:41 Z faresbasbs Cop and Robber (BOI14_coprobber) C++14
0 / 100
 4 ms 8396 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 = solve(cp,cc,moves+1,1);
		if(val < ret){
			nxt[cp][cc] = cp , ret = val;
		}
		for(auto i : graph[cp]){
			val = 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,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 Incorrect 4 ms 8392 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8392 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

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 Incorrect 4 ms 8392 KB the situation repeated
4 Halted 0 ms 0 KB -