結果
問題 | No.1123 Afforestation |
ユーザー |
![]() |
提出日時 | 2020-08-01 17:35:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 897 ms / 2,500 ms |
コード長 | 3,252 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 139,132 KB |
最終ジャッジ日時 | 2025-01-12 12:48:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 90 |
ソースコード
#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> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll INF=1e18; struct edge {int to; ll cap; int rev;} ; vector<edge> G[4040]; int level[4040]; int iter[4040]; void add_edge(int from, int to, ll cap, ll myon=0){ edge e; e.to=to, e.cap=cap-myon, e.rev=G[to].size(); G[from].push_back(e); e.to=from, e.cap=myon, e.rev=G[from].size()-1; G[to].push_back(e); } void bfs(int s){ memset(level, -1, sizeof(level)); queue<int> que; level[s]=0; que.push(s); while(!que.empty()){ int v=que.front(); que.pop(); for(int i=0; i<G[v].size(); i++){ edge e=G[v][i]; if(e.cap>0 && level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } } } ll dfs(int v, int t, ll f){ if(v==t) return f; for(int &i=iter[v]; i<G[v].size(); i++){ edge &e=G[v][i]; if(e.cap>0 && level[v]<level[e.to]){ ll d=dfs(e.to, t, min(f, e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(int s, int t){ ll flow=0; while(1){ bfs(s); if(level[t]<0) return flow; memset(iter, 0, sizeof(iter)); ll f; while((f=dfs(s, t, INF))>0){ flow+=f; } } } int z[2020][2020]; int main() { int h, w; cin>>h>>w; int a[2020], b[2020]; vector<P> va(h); int sa=0, sb=0; for(int i=0; i<h; i++){ cin>>a[i]; sa+=a[i]; va[i]=P(a[i], i); } for(int i=0; i<w; i++){ cin>>b[i]; sb+=b[i]; } if(sa!=sb){ cout<<":("<<endl; return 0; } sort(va.begin(), va.end(), greater<P>()); int cnt[2020]={}; bool dame=0; for(auto p:va){ int i=p.second; vector<P> vb(w); for(int j=0; j<w; j++) vb[j]=P(b[j]-cnt[j], j); sort(vb.begin(), vb.end(), greater<P>()); for(int j=0; j<p.first; j++){ if(vb[j].first==0){ dame=1; break; } z[i][vb[j].second]=1; cnt[vb[j].second]++; } if(dame) break; } if(dame){ cout<<":("<<endl; return 0; } string ans[2020]; for(int i=0; i<h; i++) for(int j=0; j<w; j++) ans[i]+='.'; int k; cin>>k; int x[20], y[20]; for(int i=0; i<k; i++){ cin>>x[i]>>y[i]; x[i]--; y[i]--; ans[x[i]][y[i]]='x'; } int a1[2020]={}, b1[2020]={}; for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ if(z[i][j] && ans[i][j]!='x'){ a1[i]++, b1[j]++; } } } int s=h+w, t=s+1; int sa1=0; for(int i=0; i<h; i++){ add_edge(s, i, a[i], a1[i]); sa1+=a1[i]; } for(int i=0; i<w; i++){ add_edge(i+h, t, b[i], b1[i]); } for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ if(ans[i][j]=='x') continue; add_edge(i, j+h, 1, z[i][j]); } } int f=max_flow(s, t); if(f<sa-sa1){ cout<<":("<<endl; return 0; } cout<<"Yay!"<<endl; for(int i=0; i<h; i++){ for(auto e:G[i]){ if(e.to==s) continue; if(e.cap==0){ ans[i][e.to-h]='o'; } } } for(int i=0; i<h; i++){ cout<<ans[i]<<endl; } return 0; }