| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1283200 | abc123 | Cop and Robber (BOI14_coprobber) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<bool>> adj;
// State: 2 turns - 0 (police), 1 (robber)
const int MAXN = 510;
int degree[MAXN][MAXN][2];
int dist[MAXN][MAXN][2];
int nxt[MAXN][MAXN][2]; // next move for police in police turn states
queue<tuple<int,int,int>> q;
void init() {
memset(degree, 0, sizeof(degree));
memset(dist, -1, sizeof(dist));
memset(nxt, -1, sizeof(nxt));
// Initialize degrees for states
for (int p = 0; p < N; p++) {
for (int r = 0; r < N; r++) {
degree[p][r][0] = 1; // police can wait or move to neighbors
for (int np = 0; np < N; np++)
if (adj[p][np]) degree[p][r][0]++;
degree[p][r][1] = 0; // count possible robber moves
for (int nr = 0; nr < N; nr++)
if (adj[r][nr]) degree[p][r][1]++;
}
}
}
int start_pos = -1;
void solve() {
init();
// Initialize queue with capturing states (police == robber)
for (int i = 0; i < N; i++) {
for (int turn = 0; turn < 2; turn++) {
dist[i][i][turn] = 0;
q.emplace(i, i, turn);
}
}
// Retrograde BFS from capturing states
while (!q.empty()) {
auto [p, r, turn] = q.front();
q.pop();
int curDist = dist[p][r][turn];
if (turn == 0) { // police's turn, previous turn was robber
// Previous states: robber's turn from same p but different r
// we came here from (p, r2, 1) where r2 can move to r
for (int r2 = 0; r2 < N; r2++) {
if (adj[r2][r]) {
if (dist[p][r2][1] == -1) {
degree[p][r2][1]--;
if (degree[p][r2][1] == 0) {
dist[p][r2][1] = curDist + 1;
q.emplace(p, r2, 1);
}
}
}
}
} else { // robber's turn, previous was police's turn
// Police can wait or move to neighbors
for (int p2 = 0; p2 < N; p2++) {
if (p2 == p || adj[p][p2]) {
if (dist[p2][r][0] == -1) {
dist[p2][r][0] = curDist + 1;
nxt[p2][r][0] = p; // police came from p
q.emplace(p2, r, 0);
}
}
}
}
}
// Find starting police position where police can guarantee capture
for (int p = 0; p < N; p++) {
bool canStart = true;
for (int r = 0; r < N; r++) {
if (dist[p][r][0] == -1) {
canStart = false;
break;
}
}
if (canStart) {
start_pos = p;
break;
}
}
}
// Current police position and strategy state
int policePos;
bool policeTurn = true;
int nextMove(int robberPos) {
if (policeTurn) {
// On police turn, pick next move
int nextP = -1;
// Police waits (stays) or move to neighbors
if (dist[policePos][robberPos][0] != -1) {
nextP = nxt[policePos][robberPos][0];
if(nextP == -1) nextP = policePos; // wait if no better move known
} else {
nextP = policePos;
}
policePos = nextP;
policeTurn = false;
return nextP;
} else {
// Robber turn just ended, police turn now
policeTurn = true;
// No move on robber's turn
return policePos;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
adj.assign(N, vector<bool>(N, false));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int v;
cin >> v;
adj[i][j] = (v == 1);
}
solve();
cout << start_pos << "\n";
// This is where you'd interactively run nextMove as per contest environment.
return 0;
}