Submission #127567

#	Time	Username	Problem	Language	Result	Execution time	Memory
127567		TadijaSebez	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	884 ms	7196 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int N=505;
int go[N][N],C,need[N][N][2];
bool was[N*N*2];
int H(int x, int y, int t){ return (N*x+y)*2+t;}
int start(int n, bool a[MAX_N][MAX_N])
{
	queue<int> q;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j)
	{
		int cnt=0;
		for(int k=0;k<n;k++) cnt+=a[j][k];
		need[i][j][0]=1;
		need[i][j][1]=cnt;
	}
	for(int i=0;i<n;i++)
	{
		q.push(H(i,i,0));
		q.push(H(i,i,1));
		was[H(i,i,0)]=1;
		was[H(i,i,1)]=1;
	}
	while(q.size())
	{
		int state=q.front();
		q.pop();
		int t=state%2;
		state/=2;
		int j=state%N;
		int i=state/N;
		if(t==0)
		{
			for(int k=0;k<n;k++) if(a[j][k])
			{
				need[i][k][1]--;
				if(need[i][k][1]==0)
				{
					q.push(H(i,k,1));
					was[H(i,k,1)]=1;
				}
			}
		}
		else
		{
			for(int k=0;k<n;k++) if(a[i][k] || i==k)
			{
				need[k][j][0]--;
				if(need[k][j][0]==0)
				{
					q.push(H(k,j,0));
					was[H(k,j,0)]=1;
					go[k][j]=i;
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		bool ok=1;
		for(int j=0;j<n;j++) if(!was[H(i,j,0)]) ok=0;
		if(ok)
		{
			C=i;
			return C;
		}
	}
	return -1;
}
int nextMove(int R)
{
	return C=go[C][R];
}

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