Submission #91280

#	Time	Username	Problem	Language	Result	Execution time	Memory
91280		Mohammad_Yasser	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	2 ms	384 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 505;

vector<int> adj[N];

int nxt[N][N];
bool vis[N][N][2];
int losing_children[N][N];

int current = 0;

void dfs(int cop, int robber, bool cop_turn) {
  if (vis[cop][robber][cop_turn]) {
    return;
  }
  vis[cop][robber][cop_turn] = true;

  if (cop_turn) {
    nxt[cop][robber] = cop;
    dfs(cop, robber, false);
    for (int v : adj[cop]) {
      nxt[v][robber] = cop;
      dfs(v, robber, false);
    }
  } else {
    for (int v : adj[robber]) {
      if (++losing_children[cop][v] == adj[v].size()) {
        dfs(cop, v, true);
      }
    }
  }
}

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) {
    dfs(i, i, true);
  }

  for (int i = 0; i < n; ++i) {
    bool valid = true;
    for (int j = 0; j < n; ++j) {
      valid &= vis[i][j][false];
    }
    if (valid) {
      current = i;
      return i;
    }
  }
  return -1;
}

int nextMove(int R) {
  current = nxt[current][R];
  return current;
}

Compilation message (stderr)

coprobber.cpp: In function 'void dfs(int, int, bool)':
coprobber.cpp:30:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (++losing_children[cop][v] == adj[v].size()) {
           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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