| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 726125 | Tigerpants | 경찰관과 강도 (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "coprobber.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define sz(a) a.size()
vvll g;
ll moves[MAX_N][MAX_N];
bool outcome[2][MAX_N][MAX_N]; // [turn][R][C] --> (R', C')
ll escapes[MAX_N][MAX_N];
void DFS(bool turn, ll R, ll C, ll src = -1) { // a call to DFS means that this position has just reached a positive outcome
if (outcome[turn][R][C]) return;
outcome[turn][R][C] = true;
if (turn) {
// if cop just moved
// mark all adjacent positions as positive
DFS(false, R, C, C);
for (vll::iterator itr = g[C].begin(); itr != g[C].end(); itr++) {
DFS(false, R, *itr, C);
}
} else {
moves[R][C] = src;
// if robber just moved
// remove one from escapes from all adjacent. if escapes reaches 0, then winning
for (vll::iterator itr = g[R].begin(); itr != g[R].end(); itr++) {
escapes[*itr][C]--;
if (escapes[*itr][C] == 0) {
DFS(true, *itr, C);
}
}
}
}
ll start(ll N, bool A[MAX_N][MAX_N]) {
// initialize g
g.resize(N);
rep(i, 0, N) {
rep(j, 0, N) {
if (A[i][j]) {
g[i].pb(j);
}
}
}
// initialize escapes
rep(i, 0, N) {
rep(j, 0, N) {
escapes[i][j] = sz(g[i]);
}
}
// initialize outcome
rep(i, 0, N) {
rep(j, 0, N) {
outcome[0][i][j] = false;
outcome[1][i][j] = false;
moves[i][j] = -1;
}
}
// do DFS
rep(i, 0, N) {
DFS(false, i, i, i);
DFS(true, i, i);
}
// check if all outcomes are positive
bool positive = true;
rep(i, 0, N) {
rep(j, 0, N) {
positive &= outcome[0][i][j];
positive &= outcome[1][i][j];
}
}
return positive - 1;
}
ll CopPositionNextMove = 0;
ll nextMove(ll R) {
return moves[R][CopPositionNextMove];
}