結果

問題 No.177 制作進行の宮森あおいです！
ユーザー vain0
提出日時 2015-06-01 19:05:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 2,562 bytes
コンパイル時間 812 ms
コンパイル使用メモリ 84,608 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 13:16:22
合計ジャッジ時間 1,481 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’:
main.cpp:49:61: warning: narrowing conversion of ‘graph[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   49 |         graph[from].push_back(edge { to, cap, graph[to].size() });
      |                                               ~~~~~~~~~~~~~~^~
main.cpp:50:64: warning: narrowing conversion of ‘(graph[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   50 |         graph[to].push_back(edge { from, 0, graph[from].size() - 1 });
      |                                             ~~~~~~~~~~~~~~~~~~~^~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cassert>
#include <functional>
#include <set>
#include <ctime>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#ifndef ONLINE_JUDGE //POJ
# include <random>
# include <array>
# define mkt make_tuple
# define empb emplace_back
#endif
#ifdef _LOCAL
# include "for_local.h"
#endif
using namespace std;
typedef unsigned int uint; typedef unsigned long long ull;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define mkp make_pair
#define all(_X) (_X).begin(), (_X).end()
#define scani(_V) std::scanf("%d", &_V)
#define printi(_V) std::printf("%d", static_cast<int>(_V))
//みゃーもり(0)→原画たち(2+i)→作監たち(2+n+j)→終点(2)、というDAG
//みゃーもり→原画、へはその原画が描ける枚数まで流せる
//原画と作監の間は K_n,m から「合わない組み合わせ」を取り除いたもの。ここでは任意枚の原画を流せる。
//作監→終点、へはその作監が仕上げられる枚数まで流せる
//Wカット以上流せれば万策尽きない
int const INF = 1<<29;
int const MAX_V = 2 + 50 + 50;
//蟻本p190の改変
#if 1
struct edge { int to, cap, rev; };
vector<edge> graph[MAX_V];
bool used[MAX_V];
void add_edge(int from, int to, int cap) {
    graph[from].push_back(edge { to, cap, graph[to].size() });
    graph[to].push_back(edge { from, 0, graph[from].size() - 1 });
}
int dfs(int v, int t, int f) {
    if ( v == t ) return f;
    used[v] = true;
    rep(i, graph[v].size()) {
        edge& e = graph[v][i];
        if ( !used[e.to] && e.cap > 0 ) {
            int const d = dfs(e.to, t, min(f, e.cap));
            if ( d > 0 ) {
                e.cap -= d;
                graph[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s, int t) {
    int flow = 0;
    for ( ;; ) {
        memset(used, 0, sizeof(used));
        int const f = dfs(s, t, INF);
        if ( f == 0 ) return flow;
        flow += f;
    }
}
#endif
int w, n, m;
signed main() {
    cin >> w >> n;
    rep(i, n) {
        int j; cin >> j;
        add_edge(0, 2 + i, j);
    }
    cin >> m;
    rep(i, m) {
        int c; cin >> c;
        add_edge(2 + n + i, 1, c);
    }
    rep(i, m) {
        int qi; cin >> qi;
        vector<bool> js(n, true);
        rep(j, qi) {
            int k;
            cin >> k; --k;
            js[k] = false;
        }
        rep(k, n) {
            if ( js[k] ) {
                add_edge(2 + k, 2 + n + i, INF);
            }
        }
    }
    int const max_w = max_flow(0, 1);
    cout << (max_w >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0