oj.uz

Submission #398818

# Submission time Handle Problem Language Result Execution time Memory
398818 2021-05-04T20:36:43 Z faresbasbs Cop and Robber (BOI14_coprobber) C++14
0 / 100
 86 ms 19252 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];

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);
			}
		}
	}
	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)){
				ok = 0;
				break;
			}
		}
		if(ok){
			curr = i;
			break;
		}
	}
	return 0;
}

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

Compilation message

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.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 4 ms 8392 KB Output is correct
4 Runtime error 86 ms 19252 KB Execution killed with signal 11
5 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 8264 KB Output is correct
2 Correct 6 ms 8396 KB Output is correct
3 Correct 4 ms 8392 KB Output is correct
4 Incorrect 4 ms 8392 KB the situation repeated
5 Halted 0 ms 0 KB -

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 4 ms 8392 KB Output is correct
4 Runtime error 86 ms 19252 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -