제출 #97218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97218		SpeedOfMagic	경찰관과 강도 (BOI14_coprobber)	C++17	0 / 100	19 ms	16512 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxN = 500;
const int M = 2 * maxN * maxN;
vector<int> g[maxN];
vector<int> g2[M];
 
//0 if it's officer's turn, 1 if robber's one
int enc(int officerPos, int robberPos, int whoseTurn) {
	return whoseTurn * maxN * maxN + officerPos * maxN + robberPos;
}
 
char vis[M];
int good[M];
int d[M];
void setGood(int cur) {
	vis[cur] = 1;
	if (g2[cur].empty()) {
		good[cur] = maxN;
		d[cur] = 0;
		return;
	}
	
	char robberTurn = cur / (maxN * maxN);
	good[cur] = -1;
	for (int i : g2[cur]) {
		if (!vis[i]) {
			setGood(i);
			
			if (good[i] == -1 && robberTurn) {
				good[cur] = -1;
				d[cur] = -1;
				return;
			}
		}
		
		if (good[i] != -1 && (good[cur] == -1 || d[good[cur]] > d[i]))
			good[cur] = i;
	}
	
	d[cur] = (good[cur] == -1) ? -1 : d[good[cur]] + 1;
}
 
int loc;
int start(int N, bool A[MAX_N][MAX_N]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (A[i][j]) 
				g[i].push_back(j);
			
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) 
			if (i != j) {
				g2[enc(i, j, 0)].push_back(enc(i, j, 1));
				for (int k : g[i])
					g2[enc(i, j, 0)].push_back(enc(k, j, 1));
				for (int k : g[j])
					g2[enc(i, j, 1)].push_back(enc(i, k, 1));
			}
	
	memset(vis, 0, sizeof vis);
	for (int i = 0; i < M; i++)
		if (!vis[i])
			setGood(i);
			
	for (int i = 0; i < N; i++) {
		bool no = 0;
		for (int j = 0; j < N; j++)
			no |= good[enc(i, j, 0)] == -1;
		
		if (!no) {
			loc = i;
			return i;
		}
	}
    return -1;
}
 
int nextMove(int R) {
	//cout << loc << " " << R << endl;
	loc = good[enc(loc, R, 0)] % (maxN * maxN) / maxN;
	return loc;
}

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