Submission #1307463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307463		lucaskojima	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	340 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];
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;
  bool w = false;

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

  return state[a][b][c] = (w ? 1 : 0);
}

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 i;
  }
  return -1;
}

int nextMove(int R) {
  return -1;
}

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