oj.uz

답안 #853221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853221 2023-09-23T16:29:33 Z mdobric 경찰관과 강도 (BOI14_coprobber) C++11
0 / 100
 1 ms 4636 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500

vector <int> v[505];
int dp[505][505][2];
int brojac[505][505];
int ans;
queue <pair <int, int> > q;
queue <int> red;

int start(int N, bool A[MAX_N][MAX_N]) {
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (A[i][j] == true){
				v[i].push_back(j);
			}
			dp[i][j][0] = -1;
			dp[i][j][1] = -1;
		}
	}
	
	for (int i = 0; i < N; i++){
		dp[i][i][0] = 2;
		dp[i][i][1] = 2;
		q.push(make_pair(i, i));
		red.push(0);
		q.push(make_pair(i, i));
		red.push(1);
	}
	while (!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		int r = red.front();
		q.pop();
		red.pop();
		if (dp[x][y][r] == 2 and r == 1){
			for (int i = 0; i < v[x].size(); i++){
				if (dp[v[x][i]][y][0] == -1){
					dp[v[x][i]][y][0] = 2;
					q.push(make_pair(v[x][i], y));
					red.push(0);
				}
			}
			if (dp[x][y][0] == -1){
				dp[x][y][0] = 2;
				q.push(make_pair(x, y));
				red.push(0);
			}
		}
		else
		if (dp[x][y][r] == 2 and r == 0){
			for (int i = 0; i < v[y].size(); i++){
				brojac[x][v[y][i]]++;
				if (brojac[x][v[y][i]] == v[v[y][i]].size() and dp[x][v[y][i]][1] == -2){
					dp[x][v[y][i]][1] = 2;
					q.push(make_pair(x, v[y][i]));
					red.push(1);
				}
			}
		}
	}
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (dp[i][j][0] == -1){
				dp[i][j][0] = 1;
			}
			if (dp[i][j][1] == -1){
				dp[i][j][1] = 1;
			}
		}
	}
	
	ans = -1;
	for (int i = 0; i < N; i++){
		int brojac = 0;
		for (int j = 0; j < N; j++){
			if (dp[i][j][0] == 2){
				brojac++;
			}
		}
		if (brojac == N){
			ans = i;
		}
	}
	return ans;
}

int nextMove(int R) {
	for (int i = 0; i < v[ans].size(); i++){
		if (dp[v[ans][i]][R][1] == 2){
			ans = v[ans][i];
			return ans;
		}
	}
	return ans;
}

/*
int main (void){
	
	return 0;
}
*/

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int i = 0; i < v[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~
coprobber.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int i = 0; i < v[y].size(); i++){
      |                    ~~^~~~~~~~~~~~~
coprobber.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if (brojac[x][v[y][i]] == v[v[y][i]].size() and dp[x][v[y][i]][1] == -2){
      |         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 0; i < v[ans].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4636 KB Output is correct
3 Incorrect 1 ms 4440 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4636 KB Output is correct
3 Incorrect 1 ms 4440 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -