Submission #331722

#	Time	Username	Problem	Language	Result	Execution time	Memory
331722		rqi	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	896 ms	9708 KiB

coprobber

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

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()

const int mx = 505;

int N;

pair<bool, int> dp[mx][mx][2];
int curdeg[mx][mx];
queue<pair<pi, bool>> q; 

int curpos = 0;

int start(int _N, bool A[MAX_N][MAX_N])
{
	N = _N;
	for(int i = 0; i < N; i++){
		A[i][i] = 1;
		dp[i][i][0] = dp[i][i][1] = mp(1, -1);
		q.push(mp(mp(i, i), 0)); q.push(mp(mp(i, i), 1));
	}
	for(int i = 0; i < N; i++){
		int deg = 0;
		for(int j = 0; j < N; j++){
			if(j == i) continue;
			if(A[j][i]){
				deg++;
			}
		}
		for(int j = 0; j < N; j++){
			curdeg[j][i] = deg;
		}
	}

	while(sz(q)){
		pair<pi, bool> qf = q.front();
		q.pop();
		int a = qf.f.f;
		int b = qf.f.s;
		int turn = qf.s;

		if(turn == 0){ //police's turn is a win
			for(int i = 0; i < N; i++){
				if(i == b) continue;
				if(A[i][b] && !dp[a][i][1].f){
					curdeg[a][i]--;

					if(curdeg[a][i] == 0){
						dp[a][i][1] = mp(1, b);
						q.push(mp(mp(a, i), 1));
					}
				}
			}
		}
		else{ //robber's turn is a win
			for(int i = 0; i < N; i++){
				if(A[i][a] && !dp[i][b][0].f){
					dp[i][b][0] = mp(1, a);
					q.push(mp(mp(i, b), 0));
				}
			}
		}
	}

	// for(int i = 0; i < N; i++){
	// 	for(int j = 0; j < N; j++){
	// 		for(int k = 0; k < 2; k++){
	// 			cout << i << " " << j << " " << k << " " << dp[i][j][k].f << " " << dp[i][j][k].s << "\n";
	// 		}
	// 	}
	// }
	// cout << "\n\n";

	for(int i = 0; i < N; i++){
		bool works = 1;
		for(int j = 0; j < N; j++){
			if(!dp[i][j][0].f) works = 0;
		}
		if(works){
			curpos = i;
			return i;
		}
	}
    return -1;
}

int nextMove(int R)
{
    curpos = dp[curpos][R][0].s;
    return curpos;
}

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