oj.uz

Submission #554549

# Submission time Handle Problem Language Result Execution time Memory
554549 2022-04-28T17:41:17 Z ollel Cop and Robber (BOI14_coprobber) C++14
0 / 100
 1 ms 220 KB 
using namespace std;
#include <bits/stdc++.h>

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef long long ll;
typedef pair<int,int> pii;

#include "coprobber.h"

int n;
vvi adj;
vector<set<int>> adj_set;
vector<set<int>> in_cycle;

int cop = 0;

void cycle_dfs(int x, int camefrom, vi & depth, vi & parent, vi & backDepth) { // highest depth of back edge, lowest down, max length of cycle
  backDepth[x] = depth[x];
  for (auto & j : adj[x]) {
    if (j == camefrom) continue;
    if (depth[j] == -1) {
      depth[j] = depth[x] + 1;
      parent[j] = x;
      cycle_dfs(j, x, depth, parent, backDepth);
    }
    else {
      backDepth[x] = min(backDepth[x], depth[j]);
    }
  }
}

int start(int N, bool A[MAX_N][MAX_N])
{
  n = N;
  adj.resize(n);
  rep(i,0,n) {
    rep(j,0,n) {
      if (A[i][j]) adj[i].pb(j);
    }
  }

  vi depth(n, -1);
  vi backDepth(n, -1), parent(n, -1);

  cycle_dfs(0, -1, depth, parent, backDepth);

  in_cycle.resize(n);

  rep(i,0,n) {
    int node = i, cycle = 1, back = backDepth[i];
    in_cycle[i].insert(i);
    while (depth[node] > back) {
      cycle++;
      node = parent[node];
      back = min(back, backDepth[node]);
      in_cycle[i].insert(node);
      if (cycle > 4) return -1;
    }
  }

  rep(i,0,n) for (auto & j : in_cycle[i]) in_cycle[j].insert(i);

  adj_set.resize(n);
  rep(i,0,n) for (auto & j : adj[i]) adj_set[i].insert(j);

  return 0;
}

int nextMove(int robber)
{
  if (adj_set[cop].find(robber) != adj_set[cop].end()) {
    return robber;
  }

  if (in_cycle[cop].find(robber) != in_cycle[cop].end()) {
    return cop;
  }

  vi back(n, -1);
  back[cop] = 0;
  queue<int> q; q.push(cop);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (auto j : adj[x]) {
      if (back[j] != -1) continue;
      back[j] = x;
      q.push(j);
    }
  }

  int y = robber;
  while (back[y] != cop) y = back[y];
  return y;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 220 KB Cop can catch the robber, but start() returned -1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 1 ms 208 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB the situation repeated
4 Halted 0 ms 0 KB -