結果
問題 | No.1900 Don't be Powers of 2 |
ユーザー |
![]() |
提出日時 | 2022-04-08 21:59:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 2,369 bytes |
コンパイル時間 | 2,351 ms |
コンパイル使用メモリ | 213,468 KB |
最終ジャッジ日時 | 2025-01-28 16:07:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1000000000; template <typename Cap> struct dinic{ struct edge{ int to, rev; Cap cap; edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap){ } }; int N; vector<vector<edge>> G; dinic(){ } dinic(int N): N(N), G(N){ } void add_edge(int from, int to, Cap cap){ G[from].push_back(edge(to, G[to].size(), cap)); G[to].push_back(edge(from, G[from].size() - 1, 0)); } Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){ if (v == t){ return f; } while (iter[v] < G[v].size()){ int w = G[v][iter[v]].to; if (G[v][iter[v]].cap > 0 && d[v] < d[w]){ Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap)); if (f2 > 0){ G[v][iter[v]].cap -= f2; G[w][G[v][iter[v]].rev].cap += f2; return f2; } } iter[v]++; } return 0; } Cap max_flow(int s, int t){ Cap flow = 0; while (true){ vector<int> d(N, -1); d[s] = 0; queue<int> Q; Q.push(s); while (!Q.empty()){ if (d[t] != -1){ break; } int v = Q.front(); Q.pop(); for (auto &e : G[v]){ int w = e.to; if (e.cap > 0 && d[w] == -1){ d[w] = d[v] + 1; Q.push(w); } } } if (d[t] == -1){ break; } vector<int> iter(N, 0); while (true){ Cap f = dfs(d, iter, s, t, INF); if (f == 0){ break; } flow += f; } } return flow; } }; int main(){ int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } map<int, int> mp; for (int i = 0; i < N; i++){ mp[A[i]]++; } vector<int> B, C; int M = 0; for (auto P : mp){ M++; B.push_back(P.first); C.push_back(P.second); } dinic<int> G(M + 2); for (int i = 0; i < M; i++){ if (__builtin_parity(B[i]) == 0){ for (int j = 0; j < M; j++){ if (__builtin_popcount(B[i] ^ B[j]) == 1){ G.add_edge(i, j, C[i] * C[j]); } } } } for (int i = 0; i < M; i++){ if (__builtin_parity(B[i]) == 0){ G.add_edge(M, i, C[i]); } else { G.add_edge(i, M + 1, C[i]); } } cout << N - G.max_flow(M, M + 1) << endl; }