Submission #61719

#	Time	Username	Problem	Language	Result	Execution time	Memory
61719		tmwilliamlin168	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	3 ms	384 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/n/n, c=u/n%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: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40