結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2015-04-02 23:42:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,747 bytes |
コンパイル時間 | 1,197 ms |
コンパイル使用メモリ | 101,136 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-04 01:28:04 |
合計ジャッジ時間 | 1,793 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:104:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 104 | scanf("%d", &W); | ~~~~~^~~~~~~~~~ main.cpp:106:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 106 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:108:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 108 | rep(i, N) scanf("%d", &J[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:110:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 110 | scanf("%d", &M); | ~~~~~^~~~~~~~~~ main.cpp:112:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | rep(i, M) scanf("%d", &C[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:118:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 118 | scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:122:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 122 | scanf("%d", &X), -- X; | ~~~~~^~~~~~~~~~
ソースコード
#include <string>#include <vector>#include <algorithm>#include <numeric>#include <set>#include <map>#include <queue>#include <iostream>#include <sstream>#include <cstdio>#include <cmath>#include <ctime>#include <cstring>#include <cctype>#include <cassert>#include <limits>#include <functional>#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))#if defined(_MSC_VER) || __cplusplus > 199711L#define aut(r,v) auto r = (v)#else#define aut(r,v) __typeof(v) r = (v)#endif#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)#define all(o) (o).begin(), (o).end()#define pb(x) push_back(x)#define mp(x,y) make_pair((x),(y))#define mset(m,v) memset(m,v,sizeof(m))#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLusing namespace std;typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }struct MaximumFlow {typedef int Index;typedef int Flow;static const Flow InfCapacity = INF;struct Edge {Index to;Flow capacity;Index rev;};vector<vector<Edge> > g;void init(Index n) { g.assign(n, vector<Edge>()); }void add(Index i, Index j, Flow capacity) {Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0;g[i].push_back(e); g[j].push_back(f);g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;}void addB(Index i, Index j, Flow capacity) {Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = capacity;g[i].push_back(e); g[j].push_back(f);g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;}//gを破壊するFlow maximumFlow(int s, int t) {int n = g.size();vector<Index> level(n);Flow total = 0; bool update;do {update = false;fill(level.begin(), level.end(), -1); level[s] = 0;queue<Index> q; q.push(s);for(Index d = n; !q.empty() && level[q.front()] < d; ) {int u = q.front(); q.pop();if(u == t) d = level[u];each(e, g[u]) if(e->capacity > 0 && level[e->to] == -1)q.push(e->to), level[e->to] = level[u] + 1;}vector<Index> iter(n);for(Index i = 0; i < n; i ++) iter[i] = (int)g[i].size() - 1;while(1) {Flow f = augment(level, iter, s, t, InfCapacity);if(f == 0) break;total += f; update = true;}}while(update);return total;}Flow augment(vector<Index> &level, vector<Index> &iter, Index u, Index t, Flow f) {if(u == t || f == 0) return f;Index lv = level[u];if(lv == -1) return 0;level[u] = -1;for(; iter[u] >= 0; -- iter[u]) {Edge &e = g[u][iter[u]];if(level[e.to] <= lv) continue;Flow l = augment(level, iter, e.to, t, min(f, e.capacity));if(l == 0) continue;e.capacity -= l; g[e.to][e.rev].capacity += l;level[u] = lv;return l;}return 0;}};int main() {int W;scanf("%d", &W);int N;scanf("%d", &N);vector<int> J(N);rep(i, N) scanf("%d", &J[i]);int M;scanf("%d", &M);vector<int> C(M);rep(i, M) scanf("%d", &C[i]);int src = N + M, dst = src + 1;MaximumFlow mf; mf.init(dst + 1);rep(i, N) mf.add(src, i, J[i]);rep(i, M) {int Q;scanf("%d", &Q);vector<bool> ok(N, true);rep(j, Q) {int X;scanf("%d", &X), -- X;ok[X] = false;}rep(j, N) if(ok[j])mf.add(j, N + i, INF);}rep(i, M) mf.add(N + i, dst, C[i]);int f = mf.maximumFlow(src, dst);bool ans = f >= W;puts(ans ? "SHIROBAKO" : "BANSAKUTSUKITA");return 0;}