Submission #15966

#	Time	Username	Problem	Language	Result	Execution time	Memory
15966		myungwoo	Cop and Robber (BOI14_coprobber)	C++14	60 / 100	1551 ms	202656 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];
static vector<int> con[MAXK], rcon[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;
	}
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) for (int k=0;k<2;k++){
		if (i == j) continue;
		int a = num[i][j][k];
		if (!k){
			int b = num[i][j][!k];
			con[a].pb(b); rcon[b].pb(a);
		}
		for (int t=1;t<=N;t++){
			if (!k && w[i][t]){
				int b = num[t][j][!k];
				con[a].pb(b); rcon[b].pb(a);
			}
			if (k && w[j][t]){
				int b = num[i][t][!k];
				con[a].pb(b); rcon[b].pb(a);
			}
		}
	}
	for (int i=1;i<=K;i++) deg[i] = sz(con[i]);
	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 k: rcon[q]){
				if (!V[k]) V[k] = 1, F[k] = q, que.push(k);
			}
		}else{
			for (int k: rcon[q]){
				if (!--deg[k]) V[k] = 1, F[k] = q, que.push(k);
			}
		}
	}
	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;
//		printf("Cop start at %d\n", i);
		cop_pos = i;
		return i-1;
	}
    return -1;
}

int nextMove(int x)
{
	++x;
	int to = get_dp(cop_pos, x, 0);
//	printf("Robber moved to %d\n", x);
//	printf("Then cop move to %d\n", to);
	cop_pos = to;
	return to-1;
}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:56:7: warning: unused variable 'c' [-Wunused-variable]
   int c = C[q], r = R[q], t = T[q];
       ^
coprobber.cpp:56:17: warning: unused variable 'r' [-Wunused-variable]
   int c = C[q], r = R[q], t = T[q];
                 ^

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