y2018-4-1-B

#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <memory>
#include <string>
#include <vector>

#define FILL(A, c) std::generate((A).begin(), (A).end(), []() { return (c); })
#define SORT(A, c) std::sort((A).begin(), (A).end(), (c))
#define FIND(A, c) std::find((A).begin(), (A).end(), (c))

typedef unsigned uint;
typedef std::pair<long, long> point;
struct order { long time; point from, to; order(const size_t time, const point from, const point to) : time(time), from(from), to(to) {} };
typedef std::vector<bool> bvec;
typedef std::vector<int> ivec;
typedef std::vector<ivec> matr;

class itmocar
{
  uint n_ = 0, taxi_cnt_ = 0;
  matr city_map_;
  ivec matching_;
  bvec used_, mark_;
  std::vector<order> orders_list_;

  bool check_same(const order &b)
  {
    for (const auto & a : orders_list_)
      if (a.time == b.time
        && a.to == b.to
        && a.from == b.from)
        return true;
    return false;
  }

  [[nodiscard]] long len(const point & a, const point & b) const { return abs(a.first - b.first) + abs(a.second - b.second); }

public:
  friend std::ofstream & operator<<(std::ofstream & os, const itmocar & sys)
  {
    os << sys.taxi_cnt_;
    return os;
  }

  explicit itmocar(std::ifstream & in)
  {
    char redundant;
    int hr, min, a, b, c, d;

    in >> n_;

    for (uint i = n_; i; i--)
    {
      in >> hr >> redundant >> min >> a >> b >> c >> d;
      order tmp = order(hr * 60 + min, point(a, b), point(c, d));
      // if (!check_same(tmp))
        orders_list_.emplace_back(tmp);
    }

    n_ = 2 * orders_list_.size();
    city_map_ = matr(n_, ivec());
    for (uint i = 0; i < orders_list_.size(); i++)
      for (uint j = 0; j < orders_list_.size(); j++)
      {
        if (i == j)
          continue;

        const auto A = orders_list_[i], B = orders_list_[j];
        const auto
          prev_order_endtime = A.time + len(A.from, A.to),
          move_time = len(A.to, B.from),
          delta = B.time - (prev_order_endtime + move_time);
        if (delta >= 1)
          city_map_[i].emplace_back(j + orders_list_.size());
      }
  }

  itmocar & obtain_max_matching()
  {
    // get max matching
    matching_ = ivec(n_, -1);
    used_ = bvec(n_, false);
    for (uint i = 0; i < n_; i++)
      FILL(used_, false), dfs(i);

    // cover with paths
    taxi_cnt_ = n_ / 2;
    mark_ = bvec(n_, false);
    uint match_size_ = 0;
    for (uint i = 0; i < n_; i++)
      if (matching_[i] != -1)
        mark_[i] = mark_[matching_[i]] = true, match_size_ += 2;

    for (uint i = 0; i < n_; i++)
      taxi_cnt_ -= dfs1(i);

    return *this;
  }

private:
  bool dfs(const uint v)
  {
    if (used_[v])
      return false;
    used_[v] = true;

    for (auto to : city_map_[v])
      if (matching_[to] == -1 || dfs(matching_[to]))
      {
        matching_[to] = v;
        return true;
      }
    return false;
  }

  long dfs1(const uint v)
  {
    if (used_[v] || !mark_[v])
      return 0;
    used_[v] = true;

    for (auto to : city_map_[v])
      if (!used_[to] && mark_[to])
        return 1 + dfs1(matching_[to]);
    return 1;
  }
};

int main()
{
  std::ifstream in("taxi.in");
  std::ofstream out("taxi.out");

  out << std::make_unique<itmocar>(in)->obtain_max_matching();

  out.close();
  in.close();

  return 0;
}