結果
問題 | No.1479 Matrix Eraser |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:25:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 216 ms / 3,000 ms |
コード長 | 2,305 bytes |
コンパイル時間 | 3,642 ms |
コンパイル使用メモリ | 193,156 KB |
最終ジャッジ日時 | 2025-01-20 20:09:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;struct BipartiteMatching {vector< vector< int > > graph;vector< int > match, alive, used;int timestamp;BipartiteMatching(int n) : graph(n), alive(n, 1), used(n, 0), match(n, -1), timestamp(0) {}void add_edge(int u, int v) {graph[u].push_back(v);graph[v].push_back(u);}bool dfs(int idx) {used[idx] = timestamp;for(auto &to : graph[idx]) {int to_match = match[to];if(alive[to] == 0) continue;if(to_match == -1 || (used[to_match] != timestamp && dfs(to_match))) {match[idx] = to;match[to] = idx;return true;}}return false;}int bipartite_matching() {int ret = 0;for(int i = 0; i < graph.size(); i++) {if(alive[i] == 0) continue;if(match[i] == -1) {++timestamp;ret += dfs(i);}}return ret;}void output() {for(int i = 0; i < graph.size(); i++) {if(i < match[i]) {cout << i << "-" << match[i] << endl;}}}};vector<P> v[500050];int main(){int h, w; cin>>h>>w;for(int i=0; i<h; i++){for(int j=0; j<w; j++){int a; cin>>a;v[a].push_back({i, j});}}int ans=0;for(int i=1; i<=500000; i++){if(v[i].empty()) continue;map<int, int> mp;for(auto p:v[i]){mp[p.first]=0;mp[p.second+h]=0;}int c=0;for(auto &p:mp){p.second=c++;}BipartiteMatching g(mp.size());for(auto p:v[i]){g.add_edge(mp[p.first], mp[p.second+h]);}ans+=g.bipartite_matching();}cout<<ans<<endl;return 0;}