Submission #24318

#	Time	Username	Problem	Language	Result	Execution time	Memory
24318		Bruteforceman	Cop and Robber (BOI14_coprobber)	C++11	60 / 100	1492 ms	262144 KiB

coprobber

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

struct node
{
	int move, police, thif;
	node () {}
	node (int move, int police, int thif) : move(move), police(police), thif(thif) {}
}; 

vector <node> g[2][505][505];
vector <node> t[2][505][505];
bool win[2][505][505];
int deg[2][505][505];
int cur;
node nxt[2][505][505];

int start(int N, bool A[MAX_N][MAX_N])
{
	for(int mv = 0; mv <= 1; mv++) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(mv == 0) {
					g[mv][i][j].push_back(node(mv ^ 1, i, j));
					t[mv ^ 1][i][j].push_back(node(mv, i, j));
					// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << j << endl;
				}
				for(int k = 0; k < N; k++) {
					if(mv == 0 && A[i][k]) {
						g[mv][i][j].push_back(node(mv ^ 1, k, j));
						t[mv ^ 1][k][j].push_back(node(mv, i, j));
						// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << k << "-" << j << endl;

					} else if (mv == 1 && A[j][k]) {
						g[mv][i][j].push_back(node(mv ^ 1, i, k));
						t[mv ^ 1][i][k].push_back(node(mv, i, j));
						// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << k << endl;
					}
				}
			}
		}
	}
	for(int mv = 0; mv <= 1; mv++) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				deg[mv][i][j] = g[mv][i][j].size();
			}
		}
	}
	queue <node> Q;
	memset(win, 0, sizeof win);

	for(int mv = 0; mv <= 1; mv++) {
		for(int i = 0; i < N; i++) {
			Q.push(node(mv, i, i));
			win[mv][i][i] = 1;
		}
	}

	while(!Q.empty()) {
		node n = Q.front();
		Q.pop();
		for(auto i : t[n.move][n.police][n.thif]) {
			if(win[i.move][i.police][i.thif]) continue;

			deg[i.move][i.police][i.thif]--;
			if(deg[i.move][i.police][i.thif] == 0) {

				win[i.move][i.police][i.thif] = 1;
				nxt[i.move][i.police][i.thif] = n;
				Q.push(i);
				// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
			}
			else if(i.move == 0) {
				win[i.move][i.police][i.thif] = 1;
				nxt[i.move][i.police][i.thif] = n;
				Q.push(i);

				// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
			} 
		}
	}
	// cout << nxt[0][0][2].move << " " << nxt[0][0][2].police << " " << nxt[0][0][2].thif << endl;
	for(int i = 0; i < N; i++) {
		bool sure = true;
		for(int j = 0; j < N; j++) {
			if(win[0][i][j] == 0) {
				sure = false;
			}
		}
		if(sure) {
			cur = i;
			return i;
		}
	}
    return -1;
}

int nextMove(int R)
{
	// cout << "police at: " << cur << " " << " robber at: " << R << endl;
	cur = nxt[0][cur][R].police;
    return cur;
}

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