제출 #61722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61722		tmwilliamlin168	경찰관과 강도 (BOI14_coprobber)	C++14	100 / 100	987 ms	9592 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=500;
int n, as[mxN*mxN*2], aws[mxN*mxN*2], qu[mxN*mxN*2], qh, qt, p, f[mxN*mxN];
bool a[mxN][mxN], w[mxN*mxN*2];

int start(int n2, bool a2[mxN][mxN]) {
	n=n2;
	for(int i=0; i<n; ++i)
		memcpy(a[i], a2[i], n);
	memset(as, 0, 4*n*n*2);
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			if(!a[i][j]||i==j)
				continue;
			for(int k=0; k<n; ++k) {
				++as[(i*n+k)*2];
				if(i!=j)
					++as[(k*n+i)*2+1];
			}
		}
	}
	memset(w, 0, n*n*2);
	memset(aws, 0, 4*n*n*2);
	qh=qt=0;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<2; ++j) {
			w[(i*n+i)*2+j]=1;
			qu[qt++]=(i*n+i)*2+j;
		}
	}
	while(qh<qt) {
		int u=qu[qh++], b=u/2/n, c=u/2%n, d=u%2;
		for(int i=0; i<n; ++i) {
			if(d&&(a[i][b]||i==b)&&!w[(i*n+c)*2]) {
				w[(i*n+c)*2]=1;
				qu[qt++]=(i*n+c)*2;
				f[i*n+c]=b;
			} else if(!d&&a[i][c]&&!w[(b*n+i)*2+1]) {
				++aws[(b*n+i)*2+1];
				if(aws[(b*n+i)*2+1]>=as[(b*n+i)*2+1]) {
					w[(b*n+i)*2+1]=1;
					qu[qt++]=(b*n+i)*2+1;
				}
			}
		}
	}
	p=0;
	bool ok=1;
	for(int i=0; i<n&&ok; ++i)
		ok=w[i*2];
	return ok?0:-1;
}

int nextMove(int r) {
	return p=f[p*n+r];
}

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