Submission #15985

#	Time	Username	Problem	Language	Result	Execution time	Memory
15985		myungwoo	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	860 ms	15244 KiB

coprobber

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

#define MAXK 500005
#define pb push_back
#define sz(v) ((int)(v).size())

static int N, K, cop_pos;
static int num[501][501][2], deg[MAXK];
static int C[MAXK], R[MAXK], T[MAXK], F[MAXK];
static bool w[501][501], V[MAXK];

inline int get_dp(int c, int r, int t)
{
	int n = num[c][r][t];
	if (!V[n]) return 0;
	if (!t) return C[F[n]];
	return 1;
}

int start(int n, bool A[500][500])
{
	N = n;
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) w[i][j] = A[i-1][j-1];
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) for (int k=0;k<2;k++){
		num[i][j][k] = ++K;
		C[K] = i, R[K] = j, T[K] = k;
	}
	vector <int> _deg_(N+1, 0);
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (w[i][j]) _deg_[i]++;
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (i != j){
		deg[num[i][j][1]] = _deg_[j];
	}
	queue <int> que;
	for (int i=1;i<=N;i++){
		V[num[i][i][0]] = 1, que.push(num[i][i][0]);
		V[num[i][i][1]] = 1, que.push(num[i][i][1]);
	}
	while (!que.empty()){
		int q = que.front(); que.pop();
		int c = C[q], r = R[q], t = T[q];
		if (t){
			for (int i=1;i<=N;i++) if (c == i || w[i][c]){
				int m = num[i][r][0];
				if (!V[m]) V[m] = 1, F[m] = q, que.push(m);
			}
		}else{
			for (int i=1;i<=N;i++) if (w[i][r]){
				int m = num[c][i][1];
				if (!--deg[m]) V[m] = 1, que.push(m);
			}
		}
	}
	for (int i=1;i<=N;i++){
		bool sw = 0;
		for (int j=1;j<=N;j++) if (!get_dp(i, j, 1)){ sw = 1; break; }
		if (sw) continue;
		cop_pos = i;
		return i-1;
	}
    return -1;
}

int nextMove(int x)
{
	++x;
	int to = get_dp(cop_pos, x, 0);
	cop_pos = to;
	return to-1;
}

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