Submission #91078

#	Time	Username	Problem	Language	Result	Execution time	Memory
91078		Mohammad_Yasser	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	163 ms	2880 KiB

coprobber

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

const int N = 505;

int floyd[N][N];
vector<int> adj[N];
int vis[N];
int vis_id;

int getMinCycle(int u, int v) {
  ++vis_id;
  queue<int> q;
  q.push(u);
  int level = 0;
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      int curr = q.front();
      q.pop();
      if (vis[curr] == vis_id) continue;
      vis[curr] = vis_id;
      if (curr == v) return level;
      for (int x : adj[curr]) {
        if (curr == u && x == v) continue;
        q.push(x);
      }
    }
    ++level;
  }
  return N;
}

int start(int n, bool A[MAX_N][MAX_N]) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      floyd[i][j] = (A[i][j] ? 1 : 1000);
      if (A[i][j]) {
        adj[i].push_back(j);
      }
    }
    floyd[i][i] = 0;
  }
  for (int j = 0; j < n; ++j) {
    for (int i = 0; i < n; ++i) {
      for (int k = 0; k < n; ++k) {
        floyd[i][k] = min(floyd[i][k], floyd[i][j] + floyd[j][k]);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (A[i][j]) {
        int min_cycle = getMinCycle(i, j);
        if (min_cycle != N && min_cycle >= 4) return -1;
      }
    }
    return 0;
  }
}

int current = 0;

int nextMove(int R) {
  if (floyd[current][R] == 2) return current;
  for (int x : adj[current]) {
    if (floyd[x][R] < floyd[current][R]) {
      current = x;
      return current;
    }
  }

  assert(false);
  return -1;

}

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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