Submission #84502

#	Time	Username	Problem	Language	Result	Execution time	Memory
84502		mraron	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	875 ms	7772 KiB

coprobber

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

const int COP=0, ROB=1;

int deg[501][501][2];
int ans[501][501];

int start(int N, bool A[MAX_N][MAX_N]) {
	for(int c=0;c<N;++c) {
		for(int r=0;r<N;++r) {
			deg[c][r][COP]=1;
			deg[c][r][ROB]=count(A[r], A[r]+N, true);
		}
	}
	
	queue<array<int, 3>> q;
	for(int i=0;i<N;++i) {
		deg[i][i][COP]=deg[i][i][ROB]=0;
		q.push({i,i,0});
		q.push({i,i,1});
	}
	
	int cnt=0;
	while(!q.empty()) {
		auto fr=q.front();
		q.pop();
		//cerr<<fr[0]<<" "<<fr[1]<<" "<<fr[2]<<"\n";
		cnt++;
		
		if(fr[2]==COP) {
			for(int i=0;i<N;++i) {
				if(A[i][fr[1]] && deg[fr[0]][i][ROB]) {
					deg[fr[0]][i][ROB]--;
					if(deg[fr[0]][i][ROB]==0) {
						q.push({fr[0], i, ROB});
					}
				}
			}
		}else {
			for(int i=0;i<N;++i) {
				if((fr[0]==i||A[i][fr[0]]) && deg[i][fr[1]][COP]) {
					deg[i][fr[1]][COP]--;
					if(deg[i][fr[1]][COP]==0) {
						ans[i][fr[1]]=fr[0];
						q.push({i, fr[1], COP});
					}
				}
			}
		}
	}
	//cerr<<cnt<<" "<<2*N*N<<"\n";
    return (cnt==2*N*N?0:-1);
}

int akt=0;
int nextMove(int R)
{
    return akt=ans[akt][R];
}

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