Submission #395035

#	Time	Username	Problem	Language	Result	Execution time	Memory
395035		Nicholas_Patrick	Cop and Robber (BOI14_coprobber)	C++17	30 / 100	63 ms	1916 KiB

coprobber

#include "coprobber.h"
// #include "grader.cpp"
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int sub;
int cop;
bool a[MAX_N][MAX_N];
vector<int> adjLis[MAX_N];
//sub2
int sidelength;
int start(int n, bool A[MAX_N][MAX_N]){
	for(int i=n; i--;)for(int j=n; j--;)
		a[i][j]=A[i][j];
	for(int i=n; i--;)for(int j=n; j--;){
		if(a[i][j])
			adjLis[i].push_back(j);
	}
	sub=0;
	if(sub==0){
		int edge=0;
		for(int i=n; i--;)
			edge+=adjLis[i].size();
		if(edge==n*2-2)
			sub=1;
	}
	if(sub==0){
		int edge=0;
		for(int i=n; i--;)
			edge+=adjLis[i].size();
		edge>>=1;
		for(int i=2; i<n; i++){
			if(n%i or edge!=n*2-i-n/i)
				continue;
			bool can=true;
			for(int j=n/i; j--;)for(int k=i; k--;){
				if(j and not a[j*i+k][(j-1)*i+k])
					can=false;
				if(k and not a[j*i+k][j*i+k-1])
					can=false;
			}
			if(can){
				sidelength=i;
				sub=2;
				break;
			}
		}
	}
	if(sub==0){
		if(n<=100)
			sub=3;
	}
	if(sub==0){
		sub=4;
	}
	if(sub==1){
		return cop=0;
	}
	if(sub==2){
		return cop=0;
	}
	if(sub==3){
		return -1;
		// int unlock[MAX_N][MAX_N];
		// for(int i=n; i--;)for(int j=n; j--;)
		// 	unlock[i][j]=i==j?0:(adjLis[i].size()+1)*adjLis[j].size();
		// vector<int> todo;
		// for(int i=n; i--;)
		// 	todo.push_back(i<<9|i);
		// while(not todo.empty()){
		// 	int x=todo.back();
		// 	todo.pop_back();
		// 	for(int i: adjLis[x>>9])for(int j: adjLis[x&511]){

		// 	}
		// }
		// return cop=0;
	}
	if(sub==4){
		return -1;
		//
	}
}
bool searching(int x, int p, int z){
	if(x==z)
		return true;
	for(int y: adjLis[x]){
		if(y==p)
			continue;
		if(searching(y, x, z))
			return true;
	}
	return false;
}
int nextMove(int r){
	if(sub==1){
		for(int ret: adjLis[cop]){
			if(searching(ret, cop, r)){
				return cop=ret;
			}
		}
	}
	if(sub==2){
		int cx=cop/sidelength, cy=cop%sidelength;
		int rx=r/sidelength, ry=r%sidelength;
		// printf("%d %d %d %d %d\n", cx, cy, rx, ry);
		if(rx-cx>ry-cy){
			cx++;
		}else if(rx-cx<ry-cy){
			cy++;
		}
		return cop=cx*sidelength+cy;
	}
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
   85 | }
      | ^
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

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