Submission #81214

#	Time	Username	Problem	Language	Result	Execution time	Memory
81214		wzy	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	945 ms	12284 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
bool G[505][505][2];
int R[505][505];
int AD[505];
int n;
tuple<int,int,int> P[505][505][2];
// Game Theory
// G[i][j][0] wins if  there is a k such that G[k][j][1] is winning 
// G[i][j][1] wins if all k adjacence to j G[i][k][0] is true 
int currA = 0 , currB = -1;

int start(int N, bool A[MAX_N][MAX_N])
{
	n = N;
	queue<tuple<int,int,int > > q;
 	for(int i = 0 ; i < N ; i++){
 		G[i][i][0] = 1;
 		G[i][i][1] = 1;
 		q.push(make_tuple(i,i,0));
 		q.push(make_tuple(i,i,1));
 	}
 	// fill R[][]
 	for(int i = 0 ; i < n; i++){
 		for(int j = 0 ; j < n; j ++){
 			for(int k = 0 ; k < n; k ++){
 				if(k == j) continue;
 				R[i][j] = R[i][j] + A[j][k];
 			}
 		}
 	}
 	while(!q.empty()){
 		tuple<int,int,int> u = q.front();
 		q.pop();
 		if(get<2>(u)){
 			for(int i = 0 ; i < n; i++){
 				if(A[i][get<0>(u)] || i == get<0>(u)){
 					if(G[i][get<1>(u)][0] == 0){
 						G[i][get<1>(u)][0] = 1;
 						tuple<int,int,int> t = u;
 						get<0>(t) = i, get<2>(t) = 0;
 						P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
 						q.push(t);
 					}
 				}
 			}
 		}
 		else{
 			for(int i = 0 ; i < n; i ++){
 				if(A[i][get<1>(u)]){
 					R[get<0>(u)][i]--;
	 				if(R[get<0>(u)][i] == 0){
	 					G[get<0>(u)][i][1] = true;
	 					tuple<int,int,int> t = u;
	 					get<1>(t) = i;
	 					get<2>(t) = 1;	
	 				 	P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
	 				 	 //cout<< get<0>(u) <<" " << get<1>(u) <<" " << get<2>(u) << endl;
	 				 	 //cout<< get<0>(t) <<" " << get<1>(t) <<" " << get<2>(t) << endl;
	 					q.push(t);
	 				}
 				}
 			}
 		}
 	}
 	bool can = true;
 	for(int i = 0 ; i < n; i ++){
 		if(!G[0][i][0]) can = false;
 	}
 	if(can){
 		return 0;
 	}
 	else{
 		return  -1;
 	}
}

int nextMove(int R)
{
    currB = R;
    tuple<int,int,int> L = P[currA][currB][0];
    return currA = get<0>(L);
}

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