| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 250170 | Kevin_Zhang_TW | 경찰관과 강도 (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define MAX_N 500
#define tm asdfasdfoi
const int inf = 1e9;
// modify the following functions
// you can define global variables and functions
int now, n;
vector<int> edge[MAX_N];
bool con[MAX_N][MAX_N], win[MAX_N][MAX_N];
int tm[MAX_N][MAX_N];
int lst, CT;
bool check(int a, int b) {
if (a == b) return true;
for (int u : edge[b]) {
if (!con[a][u]) return false;
}
++CT;
return true;
}
int start(int N, bool A[MAX_N][MAX_N]) {
n = N;
for (int i = 0;i < n;++i) {
for (int j = 0;j < n;++j) if (A[i][j])
con[i][j] = true, edge[i].pb(j);
con[i][i] = true;
}
for (int i = 0;i < n;++i)
for (int j = 0;j < n;++j) {
win[i][j] = check(i, j);
if (win[i][j]) tm[i][j] = ++CT;
}
bool ch = true;
while (ch) {
ch = false;
for (int i = 0;i < n;++i)
for (int j = 0;j < n;++j) if (!win[i][j]) {
bool esc = false;
for (int &l = F[i][j];l < edge[j].size();++l) {
int u = edge[j][l];
bool die = false;
for (int k : edge[i]) {
if (win[k][u]) {
die = true;
break;
}
}
die |= win[i][u];
if (!die) esc = true;
if (esc) break;
}
if (!esc) win[i][j] = true, ch = true, tm[i][j] = ++CT;
}
}
for (int i = 0;i < n;++i) {
bool allwin = true;
for (int j = 0;j < n;++j)
if (!win[i][j]) {
allwin = false;
break;
}
if (allwin) {
assert(i == 0);
return now = i;
}
}
return -1;
}
int nextMove(int R) {
if (now == R || con[now][R]) return R;
for (int u : edge[now])
if (win[u][R] && tm[u][R] < lst)
return lst = tm[u][R], now = u;
lst = tm[now][R];
return now;
}