結果
問題 | No.1479 Matrix Eraser |
ユーザー | outline |
提出日時 | 2021-04-18 15:31:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 851 ms / 3,000 ms |
コード長 | 3,629 bytes |
コンパイル時間 | 2,001 ms |
コンパイル使用メモリ | 157,216 KB |
実行使用メモリ | 18,724 KB |
最終ジャッジ日時 | 2023-09-17 07:46:24 |
合計ジャッジ時間 | 13,819 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 23 ms
4,856 KB |
testcase_08 | AC | 51 ms
6,012 KB |
testcase_09 | AC | 166 ms
9,464 KB |
testcase_10 | AC | 570 ms
14,140 KB |
testcase_11 | AC | 206 ms
10,116 KB |
testcase_12 | AC | 21 ms
5,464 KB |
testcase_13 | AC | 39 ms
5,960 KB |
testcase_14 | AC | 22 ms
5,436 KB |
testcase_15 | AC | 5 ms
4,380 KB |
testcase_16 | AC | 31 ms
5,716 KB |
testcase_17 | AC | 836 ms
15,828 KB |
testcase_18 | AC | 843 ms
15,888 KB |
testcase_19 | AC | 841 ms
15,948 KB |
testcase_20 | AC | 841 ms
15,844 KB |
testcase_21 | AC | 846 ms
16,028 KB |
testcase_22 | AC | 851 ms
15,892 KB |
testcase_23 | AC | 842 ms
16,000 KB |
testcase_24 | AC | 845 ms
16,096 KB |
testcase_25 | AC | 836 ms
15,892 KB |
testcase_26 | AC | 834 ms
15,796 KB |
testcase_27 | AC | 69 ms
8,208 KB |
testcase_28 | AC | 69 ms
8,260 KB |
testcase_29 | AC | 69 ms
8,000 KB |
testcase_30 | AC | 69 ms
8,212 KB |
testcase_31 | AC | 70 ms
8,296 KB |
testcase_32 | AC | 28 ms
7,676 KB |
testcase_33 | AC | 29 ms
7,652 KB |
testcase_34 | AC | 28 ms
7,676 KB |
testcase_35 | AC | 28 ms
7,680 KB |
testcase_36 | AC | 29 ms
7,944 KB |
testcase_37 | AC | 16 ms
4,376 KB |
testcase_38 | AC | 61 ms
7,152 KB |
testcase_39 | AC | 112 ms
18,724 KB |
testcase_40 | AC | 2 ms
4,376 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <string> #include <map> #include <set> #include <stack> #include <tuple> #include <deque> #include <array> #include <numeric> #include <bitset> #include <iomanip> #include <cassert> #include <chrono> #include <random> #include <limits> #include <iterator> #include <functional> #include <sstream> #include <fstream> #include <complex> #include <cstring> #include <unordered_map> #include <unordered_set> using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template<class T> inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template<class T> inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } struct HopcroftKarp { vector<vector<int>> graph; vector<int> dist, match; vector<bool> used, visited; HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {} void add_edge(int u, int v){ graph[u].emplace_back(v); } void bfs(){ dist.assign(graph.size(), -1); queue<int> que; for(int i = 0; i < (int)graph.size(); ++i){ if(!used[i]){ que.emplace(i); dist[i] = 0; } } while(!que.empty()){ int from = que.front(); que.pop(); for(auto& to : graph[from]){ int v = match[to]; if(v >= 0 && dist[v] == -1){ dist[v] = dist[from] + 1; que.emplace(v); } } } } bool dfs(int s){ visited[s] = true; for(auto& u : graph[s]){ int v = match[u]; if(v < 0 || (!visited[v] && dist[v] == dist[s] + 1 && dfs(v))){ match[u] = s; used[s] = true; return true; } } return false; } int bipartite_matching(){ int ret = 0; while(true){ bfs(); visited.assign(graph.size(), false); int flow = 0; for(int i = 0; i < (int)graph.size(); ++i){ if(!used[i] && dfs(i)) ++flow; } if(flow == 0) return ret; ret += flow; } } void output(){ for(int i = 0; i < (int)match.size(); ++i){ if(~match[i]){ cout << match[i] << '-' << i << '\n'; } } } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector A(H, vector<int>(W)); vector<int> vals; for(int i = 0; i < H; ++i){ for(int j = 0; j < W; ++j){ cin >> A[i][j]; if(A[i][j]) vals.emplace_back(A[i][j]); } } sort(begin(vals), end(vals)); vals.erase(unique(begin(vals), end(vals)), end(vals)); int sz = vals.size(); vector<vector<pair<int, int>>> ps(sz); for(int i = 0; i < H; ++i){ for(int j = 0; j < W; ++j){ if(!A[i][j]) continue; int k = lower_bound(begin(vals), end(vals), A[i][j]) - begin(vals); ps[k].emplace_back(i, j); } } int ans = 0; for(int i = 0; i < sz; ++i){ if(ps[i].size() <= 1) { ans += 1; continue; } HopcroftKarp g(H, W); for(auto& [x, y] : ps[i]) g.add_edge(x, y); ans += g.bipartite_matching(); } cout << ans << endl; return 0; }