結果
問題 | No.1123 Afforestation |
ユーザー | fastmath |
提出日時 | 2020-07-22 23:48:57 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 883 ms / 2,500 ms |
コード長 | 3,950 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 162,688 KB |
実行使用メモリ | 150,540 KB |
最終ジャッジ日時 | 2024-04-23 14:27:44 |
合計ジャッジ時間 | 19,625 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 3 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 5 ms
6,940 KB |
testcase_04 | AC | 25 ms
11,148 KB |
testcase_05 | AC | 426 ms
43,232 KB |
testcase_06 | AC | 869 ms
146,032 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 13 ms
7,248 KB |
testcase_12 | AC | 189 ms
27,000 KB |
testcase_13 | AC | 883 ms
149,720 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 5 ms
5,376 KB |
testcase_19 | AC | 26 ms
8,324 KB |
testcase_20 | AC | 602 ms
42,896 KB |
testcase_21 | AC | 866 ms
144,932 KB |
testcase_22 | AC | 859 ms
146,976 KB |
testcase_23 | AC | 852 ms
145,320 KB |
testcase_24 | AC | 858 ms
145,340 KB |
testcase_25 | AC | 869 ms
145,332 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 4 ms
6,940 KB |
testcase_35 | AC | 4 ms
6,944 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,948 KB |
testcase_38 | AC | 2 ms
6,944 KB |
testcase_39 | AC | 4 ms
6,944 KB |
testcase_40 | AC | 4 ms
6,940 KB |
testcase_41 | AC | 5 ms
7,928 KB |
testcase_42 | AC | 9 ms
9,312 KB |
testcase_43 | AC | 18 ms
12,452 KB |
testcase_44 | AC | 34 ms
16,720 KB |
testcase_45 | AC | 32 ms
17,012 KB |
testcase_46 | AC | 44 ms
19,448 KB |
testcase_47 | AC | 40 ms
17,472 KB |
testcase_48 | AC | 2 ms
6,940 KB |
testcase_49 | AC | 2 ms
6,944 KB |
testcase_50 | AC | 4 ms
6,940 KB |
testcase_51 | AC | 4 ms
6,944 KB |
testcase_52 | AC | 3 ms
6,944 KB |
testcase_53 | AC | 2 ms
6,940 KB |
testcase_54 | AC | 2 ms
6,944 KB |
testcase_55 | AC | 4 ms
6,944 KB |
testcase_56 | AC | 4 ms
6,944 KB |
testcase_57 | AC | 4 ms
6,944 KB |
testcase_58 | AC | 9 ms
9,316 KB |
testcase_59 | AC | 17 ms
12,332 KB |
testcase_60 | AC | 34 ms
16,356 KB |
testcase_61 | AC | 34 ms
16,048 KB |
testcase_62 | AC | 44 ms
19,464 KB |
testcase_63 | AC | 44 ms
16,544 KB |
testcase_64 | AC | 2 ms
6,944 KB |
testcase_65 | AC | 2 ms
6,944 KB |
testcase_66 | AC | 3 ms
6,940 KB |
testcase_67 | AC | 3 ms
6,944 KB |
testcase_68 | AC | 5 ms
7,980 KB |
testcase_69 | AC | 6 ms
6,940 KB |
testcase_70 | AC | 9 ms
7,268 KB |
testcase_71 | AC | 19 ms
11,264 KB |
testcase_72 | AC | 2 ms
6,940 KB |
testcase_73 | AC | 2 ms
6,944 KB |
testcase_74 | AC | 2 ms
6,944 KB |
testcase_75 | AC | 3 ms
6,944 KB |
testcase_76 | AC | 3 ms
6,940 KB |
testcase_77 | AC | 2 ms
6,944 KB |
testcase_78 | AC | 2 ms
6,940 KB |
testcase_79 | AC | 2 ms
6,944 KB |
testcase_80 | AC | 2 ms
6,940 KB |
testcase_81 | AC | 2 ms
6,940 KB |
testcase_82 | AC | 2 ms
6,940 KB |
testcase_83 | AC | 2 ms
6,944 KB |
testcase_84 | AC | 686 ms
145,876 KB |
testcase_85 | AC | 671 ms
150,540 KB |
testcase_86 | AC | 2 ms
5,376 KB |
testcase_87 | AC | 2 ms
5,376 KB |
testcase_88 | AC | 319 ms
145,120 KB |
testcase_89 | AC | 338 ms
145,344 KB |
testcase_90 | AC | 2 ms
5,376 KB |
testcase_91 | AC | 2 ms
5,376 KB |
testcase_92 | AC | 2 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC #define debug(x) std::cout << #x << ": " << x << '\n'; #define pb push_back struct Dinic{ struct edge{ int to, flow, cap; }; const static int N = 5007; //count of vertices vector<edge> e; vector<int> g[N + 7]; int dp[N + 7]; int ptr[N + 7]; void clear(){ for (int i = 0; i < N + 7; i++) g[i].clear(); e.clear(); } void addEdge(int a, int b, int cap){ g[a].pb(e.size()); e.pb({b, 0, cap}); g[b].pb(e.size()); e.pb({a, 0, 0}); } int minFlow, start, finish; bool bfs(){ for (int i = 0; i < N; i++) dp[i] = -1; dp[start] = 0; vector<int> st; int uk = 0; st.pb(start); while(uk < st.size()){ int v = st[uk++]; for (int to : g[v]){ auto ed = e[to]; if (ed.cap - ed.flow >= minFlow && dp[ed.to] == -1){ dp[ed.to] = dp[v] + 1; st.pb(ed.to); } } } return dp[finish] != -1; } int dfs(int v, int flow){ if (v == finish) return flow; for (; ptr[v] < g[v].size(); ptr[v]++){ int to = g[v][ptr[v]]; edge ed = e[to]; if (ed.cap - ed.flow >= minFlow && dp[ed.to] == dp[v] + 1){ int add = dfs(ed.to, min(flow, ed.cap - ed.flow)); if (add){ e[to].flow += add; e[to ^ 1].flow -= add; return add; } } } return 0; } int dinic(int start, int finish){ Dinic::start = start; Dinic::finish = finish; int flow = 0; for (minFlow = (1 << 30); minFlow; minFlow >>= 1){ while(bfs()){ for (int i = 0; i < N; i++) ptr[i] = 0; while(int now = dfs(start, (int)2e9 + 7)) flow += now; } } return flow; } } d; const int N = 2007; bool ban[N][N]; bool f[N][N]; int num[N][N]; signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int n, m; cin >> n >> m; vector <int> a(n), b(m); int suma = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; suma += a[i]; } int sumb = 0; for (int i = 0; i < m; ++i) { cin >> b[i]; sumb += b[i]; } if (suma != sumb) { cout << ":(" << endl; exit(0); } const int S = d.N - 2, T = d.N - 1; for (int i = 0; i < n; ++i) { d.addEdge(S, i, a[i]); } for (int i = 0; i < m; ++i) { d.addEdge(i + n, T, b[i]); } int k; cin >> k; for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; --x; --y; ban[x][y] = 1; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!ban[i][j]) { num[i][j] = d.e.size(); d.addEdge(i, j + n, 1); } } } if (d.dinic(S, T) == suma) { cout << "Yay!" << endl; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (ban[i][j]) { cout << 'x'; } else if (d.e[num[i][j]].flow) { cout << 'o'; } else { cout << '.'; } } cout << endl; } } else { cout << ":(" << endl; } }