Submission #398836

#	Time	Username	Problem	Language	Result	Execution time	Memory
398836		faresbasbs	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	678 ms	7544 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;

struct node{
	int cop,rob,tag;
};

int n,curr,moves[501][501],win[501][501][2];
queue<node> q;

int start(int N , bool grid[MAX_N][MAX_N]){
	n = N;
	for(int i = 0 ; i < n ; i += 1){
		int cnt = 0;
		for(int j = 0 ; j < n ; j += 1){
			cnt += grid[i][j];
		}
		for(int j = 0 ; j < n ; j += 1){
			if(j != i){
				win[j][i][0] = 1 , win[j][i][1] = cnt;
			}
		}
	}
	for(int i = 0 ; i < n ; i += 1){
		q.push({i,i,0}),q.push({i,i,1});
	}
	while(q.size()){
		node nxt = q.front();
		q.pop();
		if(nxt.tag == 0){
			for(int i = 0 ; i < n ; i += 1){
				if(grid[nxt.rob][i] && win[nxt.cop][i][1]){
					win[nxt.cop][i][1] -= 1;
					if(!win[nxt.cop][i][1]){
						q.push({nxt.cop,i,1});
					}
				}
			}
		}else{
			for(int i = 0 ; i < n ; i += 1){
				if(win[i][nxt.rob][0] && (i == nxt.cop || grid[nxt.cop][i])){
					win[i][nxt.rob][0] -= 1;
					q.push({i,nxt.rob,0});
					moves[i][nxt.rob] = nxt.cop;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i += 1){
		if(win[0][i][0]){
			return -1;
		}
	}
	return 0;
}

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

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