| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 233903 | parsa_mobed | Cop and Robber (BOI14_coprobber) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define pii pair <int , int>
#define F first
#define S second
#define num(i, j) i * n + j
const int N = 505;
int deg[N], Win[N][N], Cnt[N][N], Par[N][N], curPos;
int start(int n, bool A[N][N]) {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) deg[i] += A[i][j];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Cnt[i][j] = deg[j];
queue <pii> q;
for (int i = 0; i < n; i++) for (int t = 0; t < 2; t++) q.push({num(i, i), t}), Par[i][i] = i, Win[i][i] = 1;
while (!q.empty()) {
pii p = q.front(); q.pop();
int cop = p.F / n, rob = p.F % n;
if (p.S == 0) {
// Rober turn
for (int u = 0; u < n; u++)
if (A[u][cop] && !Win[u][rob])
Win[u][rob] = 1, Par[u][rob] = cop, q.push({num(u, rob), 1});
} else {
// Cop turn
for (int u = 0; u < n; u++) if (A[u][rob]) {
Cnt[cop][u]--;
if (Cnt[cop][u] == 0) q.push({num(cop, u), 0});
}
}
}
for (int i = 0; i < n; i++) {
bool Can = 1;
for (int j = 0; j < n; j++) Can &= Win[i][j];
if (Can) return curPos;
}
return -1;
}
int nextMove(int robber) {
return curPos = Par[curPos][robber];
}