結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | IL_msta |
提出日時 | 2015-08-20 23:46:17 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 2,158 bytes |
コンパイル時間 | 748 ms |
コンパイル使用メモリ | 90,852 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 11:01:18 |
合計ジャッジ時間 | 1,276 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 4 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 8 ms
6,940 KB |
testcase_10 | AC | 12 ms
6,940 KB |
testcase_11 | AC | 10 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,940 KB |
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’: main.cpp:38:34: warning: narrowing conversion of ‘V[y].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 38 | edge t = {y,cap,V[y].size() }; | ~~~~~~~~~^~ main.cpp:40:34: warning: narrowing conversion of ‘(V[x].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 40 | edge u = {x,0,V[x].size()-1 }; | ~~~~~~~~~~~^~
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <sstream> #include <algorithm> #include <cmath> #include <string> //#include <array> #include <list> #include <queue> #include <vector> #include <complex> #include <set> #include <map> ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)<<endl; #define PII pair<int,int> ///////// typedef long long LL; typedef long double LD; ///////// using namespace::std; ///////// struct edge{int to,cap,rev;}; const int Finf = (int)1e7; const int Emax = 3000; vector<edge> V[Emax]; bool use[Emax]; void add_edge(int x,int y,int cap){ edge t = {y,cap,V[y].size() }; V[x].push_back( t ); edge u = {x,0,V[x].size()-1 }; V[y].push_back( u ); } int dfs(int from,int to,int cf){ int tf; if( from == to ) return cf; use[from] = true; for(unsigned int i=0; i<V[from].size(); ++i){ edge& e = V[from][i]; if( use[e.to] == false && e.cap > 0 && ( tf = dfs(e.to,to,min(cf,e.cap)))>0){ e.cap -= tf; V[e.to][e.rev].cap += tf; return tf; } } return 0; } int maxflow(int from,int to){ int fl = 0; int tf; for(;;){ //memset(use,0,sizeof(use) ); rep(i,Emax){ use[i] = false; } tf = dfs(from,to,Finf); if( tf == 0 )return fl; fl += tf; } } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// //cout << setprecision(16);// int W,N; cin>>W>>N; rep(i,Emax){ V[i].clear(); } int sor = 0; int tin = 1; int J[50]; rep(i,N){ cin>>J[i]; add_edge( sor,i+2,J[i] ); } int M; cin>>M; int C[50]; rep(i,M){ cin>>C[i]; add_edge( 2+N+i,tin,C[i] ); } bool line[50][50]; rep(i,50)rep(j,50)line[i][j]=true; int Q,X; rep(i,M){ cin>>Q; rep(j,Q){ cin>> X; --X; //X->i //line[2+N+i][X+2] = false; //line[X+2][2+N+i] = false; line[X][i] = false; } rep(j,N){//j->i //if(line[j+2][2+N+i] == true ){ if(line[j][i] == true ){ add_edge( j+2,2+N+i,Finf ); } } } int ans; ans = maxflow(sor,tin); if( ans >= W){ cout << "SHIROBAKO\n"; }else{ cout << "BANSAKUTSUKITA\n"; } return 0; }