結果
問題 | No.1479 Matrix Eraser |
ユーザー |
|
提出日時 | 2021-04-16 21:00:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 462 ms / 3,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 5,800 ms |
コンパイル使用メモリ | 294,404 KB |
最終ジャッジ日時 | 2025-01-20 19:12:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } // N使ってる状態 0 // M使ってる状態 1 int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin >> n >> m; vector<vector<int>> a(n,vector<int>(m)); map<int,vector<pair<int,int>>> mp; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin >> a[i][j]; mp[a[i][j]].push_back({i,j}); } } int res=0; for(auto p:mp){ if(p.first==0)continue; vector<int> v,vv; for(auto pp:p.second){ v.push_back(pp.first); vv.push_back(pp.second); } sort(v.begin(), v.end()); sort(vv.begin(), vv.end()); v.erase(unique(v.begin(), v.end()),v.end()); vv.erase(unique(vv.begin(), vv.end()),vv.end()); int N=v.size(),M=vv.size(); mf_graph<int> g(N+M+2); int S=N+M,T=N+M+1; for(int i=0;i<N;i++){ g.add_edge(i,T,1); } for(int i=0;i<M;i++){ g.add_edge(S,N+i,1); } for(auto pp:p.second){ g.add_edge(N+(lower_bound(vv.begin(), vv.end(),pp.second)-vv.begin()),(lower_bound(v.begin(), v.end(),pp.first)-v.begin()),1e9); } res+=g.flow(S,T); } cout << res << endl; }