Submission #338082

#	Time	Username	Problem	Language	Result	Execution time	Memory
338082		CaroLinda	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	1 ms	492 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
#define debug printf
#define ll long long

const int MAXN = 510 ;

using namespace std ;

int outDeg[MAXN][MAXN][2] ;
bool graph[MAXN][MAXN] ;
bool isWinner[MAXN][MAXN][2] ;
int myCurrent , n ;

int start(int N, bool A[MAX_N][MAX_N])
{
	n = N ;

	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < N ; j++ )
			graph[i][j] = A[i][j] ;

	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < N ; j++ )
			for(int k = 0 ; k < 2 ; k++ )
			{
				isWinner[i][j][k] = k ? true : false ;

				if( i == j && k == 1 ) continue ;

				if(!k) 
				{
					for(int g = 0 ; g < N ; g++ )
						if( A[i][g] ) outDeg[i][j][k]++ ;

					outDeg[i][j][k]++ ;
				}

				else
				{
					for(int g = 0 ; g < N ; g++ )
						if( A[j][g] ) outDeg[i][j][k]++ ;
				}

			}

	vector< tuple<int,int,int> > q ;
	int ini = 0 ;

	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < N ; j++ )
			for(int k = 0 ; k < 2 ; k++ )
				if( outDeg[i][j][k] == 0 ) q.push_back( make_tuple(i,j,k) ) ;

	while( ini < sz(q) )
	{

		int x = get<0>( q[ini] ) ;
		int y = get<1>( q[ini] ) ;
		int z = get<2>( q[ini] ) ;

		ini++ ;

		isWinner[x][y][z] = z ? false : true ;

		//cout << x << " " << y << " " << z << endl ;

		if(!z)
		{
			//I'm the cop's turn
			//That means my previous must be a robber's move

			for(int i = 0 ; i < N ; i++ )
				if( A[i][y] && (--outDeg[x][i][1]) == 0 ) q.push_back( make_tuple(x,i,1) ) ;

		}
		else
		{
			for(int i = 0 ; i < N ; i++ )
			{
				if( !A[i][x] && i != x ) continue ;
				
				outDeg[i][y][1] = 0 ;

				q.push_back( make_tuple(i,y,0) ) ;

			}
		}	

	}

	for(int i = 0 ; i < N ; i++ )
	{
		bool theyWin = true ;

		for(int j = 0 ; j < N ; j++ )
			theyWin &= isWinner[i][j][0] ;

		if( theyWin ) return myCurrent = i ;	
	}

	return -1 ;

}

int nextMove(int R)
{

	//The state is (myCurrent, R, 0) 

	for(int i = 0 ; i < n ; i++ )
		if( (graph[i][myCurrent] || myCurrent == i ) && !isWinner[i][R][1] ) return myCurrent = i ;

}

Compilation message (stderr)

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

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