結果

問題 No.3345 Reducible Sequence
コンテスト
ユーザー テナガザル
提出日時 2025-11-13 23:27:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,795 ms / 2,000 ms
コード長 2,328 bytes
コンパイル時間 1,520 ms
コンパイル使用メモリ 115,472 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-13 23:27:44
合計ジャッジ時間 6,690 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

template<typename T>
class maxflow
{
  struct edge {int to, rep; T cap; edge(int t, int r, T c) : to(t), rep(r), cap(c) {}};
  std::vector<std::vector<edge>> g;
  public:
  std::vector<int> dis, id;
  maxflow(int n) : g(n), id(n), dis(n) {}
  void add_edge(int s, int t, T f)
  {
    g[s].push_back({t, (int)g[t].size() + (s == t), f});
    g[t].push_back({s, (int)g[s].size() - 1, 0});
  }
  T flow(int s, int t)
  {
    T ret = 0;
    while (bfs(s, t))
    {
      id.assign(id.size(), 0);
      ret += path(s, t, T((1LL << 60) | (1 << 30)));
    }
    return ret;
  }
  bool bfs(int s, int t)
  {
    dis.assign(g.size(), g.size());
    dis[s] = 0;
    std::queue<int> q;
    for (q.push(s); !q.empty(); q.pop())
    {
      int now = q.front();
      for (auto &v : g[now])
      {
        if (v.cap > 0 && dis[v.to] > dis[now] + 1)
        {
          dis[v.to] = dis[now] + 1;
          q.push(v.to);
        }
      }
    }
    return dis[t] < g.size();
  }
  T path(int s, int t, T lim)
  {
    if (s == t) return lim;
    T now = 0;
    for (int &i = id[t]; i < g[t].size(); ++i)
    {
      auto &e = g[t][i], &re = g[e.to][e.rep];
      if (re.cap <= 0 || dis[e.to] >= dis[t] || dis[e.to] < 0) continue;
      T tmp = path(s, e.to, std::min(lim - now, re.cap));
      if (tmp == 0) continue;
      e.cap += tmp;
      re.cap -= tmp;
      now += tmp;
      if (now >= lim) break;
    }
    return now;
  }
};

int main()
{
  int n;
  cin >> n;
  vector<int> a(5001, -1), cnt(5001);
  for (int i = 0; i < n; ++i)
  {
    int v;
    cin >> v;
    a[v] = i;
    ++cnt[v];
  }
  maxflow<int> mf(n + n + 2);
  int sorce = n + n, sink = sorce + 1;
  int pos = 0;
  for (int i = 1; i <= 5000; ++i)
  {
    if (cnt[i])
    {
      mf.add_edge(sorce, pos, cnt[i]);
      a[i] = pos;
      ++pos;
    }
  }
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; i * j <= 5000; ++j)
    {
      if (a[i * j] >= 0) mf.add_edge(a[i * j], n + i - 1, 1);
    }
  }
  int ans = n;
  for (int i = 0; i < n; ++i)
  {
    mf.add_edge(n + i, sink, 1);
    if (mf.bfs(sorce, sink))
    {
      mf.id.assign(mf.id.size(), 0);
      mf.path(sorce, sink, 1);
    }
    else
    {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
}
0