Submission #119151

#	Time	Username	Problem	Language	Result	Execution time	Memory
119151		imyujin	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	589 ms	8928 KiB

coprobber

#include "coprobber.h"
#include<queue>
#include<tuple>

using namespace std;

typedef tuple<int, int, int> tiii;

const int INF=MAX_N*MAX_N;

bool adj[MAX_N][MAX_N];
bool chk[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][2], deg[MAX_N][MAX_N];
queue<tiii> q;
int p;

int start(int N, bool A[MAX_N][MAX_N]){
	for(int i=0; i<N; i++) for(int j=0; j<N; j++){
		adj[i][j]=A[i][j];
		dp[i][j][0]=dp[i][j][1]=-1;
		if(A[i][j]) deg[0][i]++;
	}
	for(int i=0; i<N; i++) for(int j=1; j<N; j++) deg[j][i]=deg[0][i];
	for(int i=0; i<N; i++){
		q.push(make_tuple(i, i, 0));
		q.push(make_tuple(i, i, 1));
		dp[i][i][0]=dp[i][i][1]=0;
	}
	while(!q.empty()){
		int c, r, t;
		tie(c, r, t)=q.front();
		q.pop();
		//printf("[%d %d %d]\n", c, r, t);
		if(t==0){
			for(int i=0; i<N; i++) if(A[i][r]&&dp[c][i][1]==-1){
				deg[c][i]--;
				if(deg[c][i]==0){
					//printf("(%d %d %d)\n", c, i, 1);
					q.push(make_tuple(c, i, 1));
					dp[c][i][1]=dp[c][r][t]+1;
				}
			}
		}
		else{
			for(int i=0; i<N; i++) if((c==i||A[c][i])&&dp[i][r][0]==-1){
				//printf("(%d %d %d)\n", i, r, 0);
				q.push(make_tuple(i, r, 0));
				dp[i][r][0]=dp[c][r][t]+1;
			}
		}
	}

	/*
	for(int k=0; k<2; k++){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++) printf("%d ", dp[i][j][0]);
		printf("\n");
	}
	printf("****\n");
	}
	*/
	
	for(int i=0; i<N; i++){
		bool b=true;
		for(int j=0; j<N; j++) if(dp[i][j][0]==-1) b=false;
		if(b) return p=i;
	}
	return -1;
}

int nextMove(int R){
	for(int i=0;; i++) if((adj[p][i]||i==p)&&dp[i][R][1]==dp[p][R][0]-1) return p=i;
	//return -1;
}

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