結果

問題 No.141 魔法少女コバ
コンテスト
ユーザー OnjoujiToki
提出日時 2025-12-17 15:29:37
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 5,794 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,505 ms
コンパイル使用メモリ 131,360 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-17 15:29:42
合計ジャッジ時間 4,785 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 93
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>  // credit atcoder
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>

/*
g++ -std=c++23 -O2 -Wall -Wextra A.cpp -o A
./A < input.in > output.out


*/
// credit atcoder

// https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md
namespace internal {

template <class T>
struct simple_queue {
  std::vector<T> payload;
  int pos = 0;
  void reserve(int n) { payload.reserve(n); }
  int size() const { return int(payload.size()) - pos; }
  bool empty() const { return pos == int(payload.size()); }
  void push(const T& t) { payload.push_back(t); }
  T& front() { return payload[pos]; }
  void clear() {
    payload.clear();
    pos = 0;
  }
  void pop() { pos++; }
};

}  // namespace internal

template <class Cap>
struct mf_graph {
 public:
  mf_graph() : _n(0) {}
  mf_graph(int n) : _n(n), g(n) {}

  int add_edge(int from, int to, Cap cap) {
    assert(0 <= from && from < _n);
    assert(0 <= to && to < _n);
    assert(0 <= cap);
    int m = int(pos.size());
    pos.push_back({from, int(g[from].size())});
    g[from].push_back(_edge{to, int(g[to].size()), cap});
    g[to].push_back(_edge{from, int(g[from].size()) - 1, 0});
    return m;
  }

  struct edge {
    int from, to;
    Cap cap, flow;
  };

  edge get_edge(int i) {
    int m = int(pos.size());
    assert(0 <= i && i < m);
    auto _e = g[pos[i].first][pos[i].second];
    auto _re = g[_e.to][_e.rev];
    return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
  }
  std::vector<edge> edges() {
    int m = int(pos.size());
    std::vector<edge> result;
    for (int i = 0; i < m; i++) {
      result.push_back(get_edge(i));
    }
    return result;
  }
  void change_edge(int i, Cap new_cap, Cap new_flow) {
    int m = int(pos.size());
    assert(0 <= i && i < m);
    assert(0 <= new_flow && new_flow <= new_cap);
    auto& _e = g[pos[i].first][pos[i].second];
    auto& _re = g[_e.to][_e.rev];
    _e.cap = new_cap - new_flow;
    _re.cap = new_flow;
  }

  Cap flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); }
  Cap flow(int s, int t, Cap flow_limit) {
    assert(0 <= s && s < _n);
    assert(0 <= t && t < _n);

    std::vector<int> level(_n), iter(_n);
    internal::simple_queue<int> que;

    auto bfs = [&]() {
      std::fill(level.begin(), level.end(), -1);
      level[s] = 0;
      que.clear();
      que.push(s);
      while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto e : g[v]) {
          if (e.cap == 0 || level[e.to] >= 0) continue;
          level[e.to] = level[v] + 1;
          if (e.to == t) return;
          que.push(e.to);
        }
      }
    };
    auto dfs = [&](auto self, int v, Cap up) {
      if (v == s) return up;
      Cap res = 0;
      int level_v = level[v];
      for (int& i = iter[v]; i < int(g[v].size()); i++) {
        _edge& e = g[v][i];
        if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
        Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
        if (d <= 0) continue;
        g[v][i].cap += d;
        g[e.to][e.rev].cap -= d;
        res += d;
        if (res == up) break;
      }
      return res;
    };

    Cap flow = 0;
    while (flow < flow_limit) {
      bfs();
      if (level[t] == -1) break;
      std::fill(iter.begin(), iter.end(), 0);
      while (flow < flow_limit) {
        Cap f = dfs(dfs, t, flow_limit - flow);
        if (!f) break;
        flow += f;
      }
    }
    return flow;
  }

  std::vector<bool> min_cut(int s) {
    std::vector<bool> visited(_n);
    internal::simple_queue<int> que;
    que.push(s);
    while (!que.empty()) {
      int p = que.front();
      que.pop();
      visited[p] = true;
      for (auto e : g[p]) {
        if (e.cap && !visited[e.to]) {
          visited[e.to] = true;
          que.push(e.to);
        }
      }
    }
    return visited;
  }

 private:
  int _n;
  struct _edge {
    int to, rev;
    Cap cap;
  };
  std::vector<std::pair<int, int>> pos;
  std::vector<std::vector<_edge>> g;
};

template <typename T>
struct Dijkstra {
  using edge = std::pair<T, int>;  // weight & vertex id num
  const T INF = std::numeric_limits<T>::max() / 2;
  int n;
  std::vector<std::vector<edge>> edges;
  Dijkstra(int _n) : n(_n), edges(n) {}

  // Add a directed edge from u -> v;
  void add_edge(int u, int v, T weight) { edges[u].emplace_back(weight, v); }
  // return dist [0..n - 1] pred[0..n - 1]
  std::pair<std::vector<T>, std::vector<int>> shortest_paths(int s) {
    std::vector<T> dist(n, INF);
    std::vector<int> pred(n, -1);
    dist[s] = 0;
    std::priority_queue<edge, std::vector<edge>, std::greater<edge>> pq;
    pq.emplace(0, s);

    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (d == dist[u]) {
        for (auto [w, v] : edges[u]) {
          if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pred[v] = u;
            pq.emplace(dist[v], v);
          }
        }
      }
    }
    return {dist, pred};
  }

  std::vector<int> get_path(int v, const std::vector<int>& pred) {
    std::vector<int> path = {v};
    while (pred[v] != -1) {
      path.push_back(pred[v]);
      v = pred[v];
    }

    reverse(path.begin(), path.end());
    return path;
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m;
  std::cin >> n >> m;
  int ans = 0;
  while (m) {
    if (n < m) {
      ans += 1;
      std::swap(n, m);
    } else {
      int q = n / m;
      ans += q;
      n -= q * m;
    }
  }
  std::cout << ans -2 << "\n";
  return 0;
}
0