Submission #974819

#	Time	Username	Problem	Language	Result	Execution time	Memory
974819		MilosMilutinovic	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	40 ms	12336 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int cur;
bool dp[N][N][2];
vector<int> g[N];
int deg[N][N][2];
int to[N][N];

int start(int n, bool A[MAX_N][MAX_N]) { 
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (!A[i][j]) {
        continue;
      }
      g[i].push_back(j);
      g[j].push_back(i);
    }
  }
  vector<array<int, 3>> que;
  for (int i = 0; i < n; i++) {
    dp[i][i][0] = true;
    dp[i][i][1] = true;
    que.push_back({i, i, 0});
    que.push_back({i, i, 1});
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      deg[i][j][1] = (int) g[j].size();
    }
  }
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b][0];
    int j = que[b][1];
    int t = que[b][2];
    if (t == 0) {
      for (int k : g[j]) {
        deg[i][k][1]--;
        if (deg[i][k][1] <= 0 && !dp[i][k][1]) {
          dp[i][k][1] = true;
          que.push_back({i, k, 1});
        }
      }
    } else {
      for (int k : g[i]) {
        if (!dp[k][j][0]) {
          dp[k][j][0] = true;
          to[k][j] = i;
          que.push_back({k, j, 0});
        }
      }
    }
  }
  cur = -1;
  for (int i = 0; i < n; i++) {
    bool ok = true;
    for (int j = 0; j < n; j++) {
      if (!dp[i][j][0]) {
        ok = false;
      }
    }
    if (ok) {
      cur = i;
      break;
    }
  }
  return cur;
}

int nextMove(int r) {
  cur = to[cur][r];
  return cur;
}

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