Submission #853514

#	Time	Username	Problem	Language	Result	Execution time	Memory
853514		mdobric	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	511 ms	10012 KiB

coprobber

#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 potez[505][505];

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;
					potez[v[x][i]][y] = x;
					q.push(make_pair(v[x][i], y));
					red.push(0);
				}
			}
			if (dp[x][y][0] == -1){
				dp[x][y][0] = 2;
				potez[x][y] = x;
				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] == -1){
					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) {
	ans = potez[ans][R];
	return ans;
}

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

Compilation message (stderr)

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

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40