#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;
cout << "DFS(" << turn << ", " << R << ", " << C << ", " << src << ")\n";
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);
}
}
}
}
int start(int 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;
int nextMove(int R) {
return moves[R][CopPositionNextMove];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
336 KB |
HACKED |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
336 KB |
HACKED |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
0 ms |
336 KB |
HACKED |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Failed |
1 ms |
336 KB |
HACKED |
| 2 |
Halted |
0 ms |
0 KB |
- |
