Submission #1307466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307466		lucaskojima	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	46 ms	27796 KiB

coprobber

#include "coprobber.h"
#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int state[MAX_N][MAX_N][2];
int pos[MAX_N][MAX_N];
vector<int> adj[MAX_N];

int f(int a, int b, int c) {
  if (state[a][b][c] != -1) return state[a][b][c];
  if (a == b)
    return state[a][b][c] = (c == 0 ? 1 : 0);

  state[a][b][c] = 2;
  int w = 0;

  if (c == 0) { // cop
    int v = f(a, b, !c);
    if (v == 0) {
      w = 1;
      pos[a][b] = a;
    }

    for (int k : adj[a]) {
      int v = f(k, b, !c);
      if (v == 0) {
        w = 1;
        pos[a][b] = k;
      }
    }
  } else { // robber
    for (int k : adj[b]) {
      int v = f(a, k, !c);
      if (v == 0 || v == 2)
        w = 1;
    }
  }

  return state[a][b][c] = w;
}

int P;

int start(int N, bool A[MAX_N][MAX_N]) {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (A[i][j])
        adj[i].push_back(j);

  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < 2; k++)
        state[i][j][k] = -1;

  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++)
      if (f(i, j, 0) == 1)
        cnt++;

    if (cnt == N)
      return P = i;
  }
  return -1;
}

int nextMove(int R) {
  return P = pos[P][R];
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40