제출 #554531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554531		ollel	경찰관과 강도 (BOI14_coprobber)	C++14	컴파일 에러	0 ms	0 KiB

coprobber

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] - 1;
  for (auto & j : adj[x]) {
    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, vector<vector<bool>> A)
{
  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_cylce[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]) {
      back[j] = x;
      q.push(j);
    }
  }

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

컴파일 시 표준 에러 (stderr) 메시지

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:80:7: error: 'in_cylce' was not declared in this scope; did you mean 'in_cycle'?
   80 |   if (in_cylce[cop].find(robber) != in_cycle[cop].end()) {
      |       ^~~~~~~~
      |       in_cycle