Submission #853210

# Submission time Handle Problem Language Result Execution time Memory
853210 2023-09-23T16:14:14 Z mdobric Cop and Robber (BOI14_coprobber) C++11
0 / 100
2 ms 4440 KB
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500

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

void dfs (int poc, int x){
	for (int i = 0; i < v[x].size(); i++){
		if (dist[poc][v[x][i]] == -1){
			dist[poc][v[x][i]] = dist[poc][x] + 1;
			dfs(poc, v[x][i]);
		}
	}
	return;
}

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;
			dist[i][j] = -1;
		}
	}
	for (int poc = 0; poc < N; poc++){
		dist[poc][poc] = 0;
		dfs(poc, poc);
	}
	/*
	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()){
					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;
		}
	}
	*/
	ans = 0;
	return 0;
}

int nextMove(int R) {
	int min_dist = dist[ans][R], in;
	for (int i = 0; i < v[ans].size(); i++){
		if (dist[v[ans][i]][R] < min_dist){
			min_dist = dist[v[ans][i]][R];
			in = v[ans][i];
		}
	}
	return in;
}

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

Compilation message

coprobber.cpp: In function 'void dfs(int, int)':
coprobber.cpp:15:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int i = 0; i < v[ans].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
coprobber.cpp:117:9: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |  return in;
      |         ^~
# Verdict Execution time Memory 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 the situation repeated
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4440 KB the situation repeated
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4440 KB the situation repeated
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory 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 the situation repeated
4 Halted 0 ms 0 KB -