제출 #1125839

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

coprobber

#include "coprobber.h"
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
const int MOD = 1e9 + 7;
const int inf = 2e9;
bool w[MAX_N][MAX_N];
bool f[MAX_N][MAX_N][2];
int vis[MAX_N][MAX_N][2], opt[MAX_N][MAX_N];
vector<int> g[MAX_N];
int pre;

bool calc(int u, int v, int steps) {
	if(u == v) {
		return f[u][v][steps] = 1;
	}
	if(vis[u][v][steps] == 2) return f[u][v][steps];
	vis[u][v][steps] = 1;
	if(steps & 1) {
		bool ans = 0;
		for(int x : g[u]) {
			if(vis[x][v][0] == 1) {
				continue;
			}
			if(calc(x, v, 0)) opt[u][v] = x;
			ans = ans | calc(x, v, 0); 
		}
		if(vis[u][v][0] != 1) ans = ans | calc(u, v, 0);
		if(calc(u, v, 0)) opt[u][v] = u;
		vis[u][v][steps] = 2;
		return f[u][v][steps] = ans;
	} else {
		bool ans = 1;
		for(int x : g[v]) {
			if(vis[u][x][1] == 1) {
				ans = 0;
				break;
			}
			ans = ans & calc(u, x, 1);
		}
		vis[u][v][steps] = 2;
		return f[u][v][steps] = ans;
	}
}

int start(int N, bool A[MAX_N][MAX_N]) {
	int n = N;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			w[i][j] = A[i][j];
			if(w[i][j]) {
				g[i].pb(j);
			}
		}
	}
	int ans = -1;
	for(int i = 0; i < n; i++) {
		bool cur = 1;
		for(int j = 0; j < n; j++) {
			cur = cur & calc(i, j, 1);
		}
		if(cur) {
			pre = i;
			return i;
		}
	}
	return ans;
}

int nextMove(int x) {
	pre = opt[pre][x];
	return pre;
}

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