結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | なお |
提出日時 | 2015-04-03 23:35:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,867 bytes |
コンパイル時間 | 1,748 ms |
コンパイル使用メモリ | 176,880 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 01:40:16 |
合計ジャッジ時間 | 2,110 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef vector<VI> VVI; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) #define FOR(i, f, t) for(int(i)=(f);(i)<(t);(++i)) #define RREP(i, n) for(int(i)=(n)-1;(i)>=0;--(i)) #define FOREACH(it, c) for(auto it=(c).begin();it!=(c).end();++it) const int MOD = int(1e9+7); // Dinic class MaxFlow { int sa(int a, int b){ll c=(ll)a+b;return int(c<INF?c:INF);} int aug(const int u, const int t, const VI &P, VI &fin, int cur){ if(u == t || cur == 0) return cur; if(fin[u]) return 0; fin[u] = true; int m = 0; FOREACH(it, E[u]){ const int &v = *it; if(P[v] <= P[u]) continue; m = aug(v, t, P, fin, min(cur, C[u][v] - F[u][v])); if(m > 0){ F[u][v] += m; F[v][u] -= m; fin[u] = false; break; } } return m; } public: static const int INF = 1<<29; VVI C, E, F; MaxFlow(int n) : C(n, VI(n)), E(n), F(n, VI(n)){;} void set(int u, int v, int c){ if(C[u][v] == 0 && C[v][u] == 0) E[u].push_back(v); E[v].push_back(u); C[u][v] = c; } void add(int u, int v, int c){ set(u,v,sa(C[u][v],c));} int solve(const int s, const int t){ int n = C.size(), f = 0; VI P(n), M(n); bool cont = true; while(cont){ P = VI(n,-1); P[s] = 0; queue<int> q; q.push(s); for(int d = n; !q.empty() && P[q.front()] < d; ){ int u = q.front(); q.pop(); if(u == t) d = P[u]; FOREACH(it, E[u]){ const int &v = *it; if(P[v] >= 0 || C[u][v] - F[u][v] <= 0) continue; P[v] = P[u]+1; q.push(v); } } VI fin(n); cont = false; while(1){ int m = aug(s, t, P, fin, INF); if(m == 0) break; f += m; cont = true; } } return f; } }; int W,N,J[55],M,C[55]; int res = 0; int main(){ do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0); cin >> W >> N; REP(i,N) cin >> J[i]; cin >> M; REP(i,M) cin >> C[i]; set<int> X[55]; REP(i,M){ int Q,x; cin >> Q; REP(j,Q){ cin >> x; X[i].insert(x-1); } } // 0~49 : 原画(N) // 50~99 : 作監(M) // 100 : s // 101 : t MaxFlow mf(102); int s = 100, t = 101; REP(i,N) mf.set(s,i,J[i]); REP(i,M){ const auto &x = X[i]; REP(j,N){ if(x.count(j)) continue; mf.set(j,50+i,mf.INF); } mf.set(50+i,t,C[i]); } cout << (mf.solve(s,t) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl; return 0; }