結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | threepipes_s |
提出日時 | 2015-12-14 15:17:14 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 4,315 bytes |
コンパイル時間 | 2,530 ms |
コンパイル使用メモリ | 77,388 KB |
実行使用メモリ | 55,512 KB |
最終ジャッジ日時 | 2023-10-13 16:33:01 |
合計ジャッジ時間 | 4,770 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 49 ms
49,632 KB |
testcase_01 | AC | 51 ms
49,652 KB |
testcase_02 | AC | 48 ms
49,648 KB |
testcase_03 | AC | 80 ms
51,876 KB |
testcase_04 | AC | 79 ms
52,368 KB |
testcase_05 | AC | 117 ms
55,468 KB |
testcase_06 | AC | 117 ms
53,976 KB |
testcase_07 | AC | 58 ms
50,144 KB |
testcase_08 | AC | 93 ms
53,280 KB |
testcase_09 | AC | 138 ms
55,200 KB |
testcase_10 | AC | 150 ms
55,512 KB |
testcase_11 | AC | 140 ms
55,268 KB |
testcase_12 | AC | 134 ms
54,104 KB |
testcase_13 | AC | 47 ms
49,880 KB |
testcase_14 | AC | 47 ms
49,516 KB |
testcase_15 | AC | 47 ms
49,420 KB |
ソースコード
import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; import java.util.List; public class Main { public static void main(String[] args) throws NumberFormatException, IOException {Solve solve = new Solve();solve.solve();} } class Solve{ void solve() throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner(); Writer out = new Writer(); int w = in.nextInt(); int n = in.nextInt(); int[] j = new int[n]; for(int i=0; i<n; i++) j[i] = in.nextInt(); int m = in.nextInt(); int s = n+m; int t = n+m+1; MaxFlow mf = new MaxFlow(n+m+2, s, t); for(int i=0; i<n; i++) mf.edge(s, i, j[i]); for(int i=0; i<m; i++) mf.edge(n+i, t, in.nextInt()); BitSet fob = new BitSet(n); for(int i=0; i<m; i++){ int q = in.nextInt(); fob.clear(); for(int k=0; k<q; k++){ fob.set(in.nextInt()-1); } for(int k=fob.nextClearBit(0) ; k<n; k=fob.nextClearBit(k+1)){ mf.edge(k, n+i, MaxFlow.inf); } } System.out.println(mf.solve()<w?"BANSAKUTSUKITA":"SHIROBAKO"); } } class MaxFlow{ int n, s, t; List<Edge>[] node; MaxFlow(int n, int s, int t) { this.n=n;this.s=s;this.t=t;node=new List[n]; for(int i=0;i<n;i++)node[i]=new ArrayList<>(); used = new BitSet(n); } void edge(int a, int b, int c){ Edge ae = new Edge(b, c); Edge be = new Edge(a, 0); ae.rev = be; be.rev = ae; node[a].add(ae); node[b].add(be); } void edge(int a, int b, int c, int rc){ Edge ae = new Edge(b, c); Edge be = new Edge(a, rc); ae.rev = be; be.rev = ae; node[a].add(ae); node[b].add(be); } final static int inf = Integer.MAX_VALUE/2; int solve(){ int res = 0; while(true){ used.clear(); int flow = flow(s, inf); if(flow == 0) break; res += flow; } return res; } BitSet used; int flow(int from, int flow){ if(from == t) return flow; if(used.get(from)) return 0; used.set(from); for(Edge e: node[from]){ final int cap = e.cap; if(cap==0) continue; int f = flow(e.to, Math.min(flow, cap)); if(f == 0) continue; e.cap -= f; e.rev.cap += f; return f; } return 0; } class Edge{ int to,cap; Edge rev; Edge(int t, int c){to=t;cap=c;} } } class MultiSet<T> extends HashMap<T, Integer>{ @Override public Integer get(Object key){return containsKey(key)?super.get(key):0;} public void add(T key,int v){put(key,get(key)+v);} public void add(T key){put(key,get(key)+1);} public void sub(T key){ final int num = get(key); if(num==1) remove(key); else put(key, num-1); } } class Timer{ long time; public void set(){time = System.currentTimeMillis();} public long stop(){return System.currentTimeMillis()-time;} } class Writer extends PrintWriter{ public Writer(String filename) throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer() throws IOException{super(System.out);} } class ContestScanner { private InputStreamReader reader;int c; public ContestScanner() throws IOException {reader = new InputStreamReader(System.in);c=reader.read();} public ContestScanner(String filename) throws IOException {reader = new InputStreamReader(new FileInputStream(filename));c=reader.read();} public String nextToken() throws IOException { StringBuilder sb = new StringBuilder(); while(c!=-1&&(c==' '||c=='\t'||c=='\n'||c=='\r'))c=reader.read(); while(c!=-1&&c!=' '&&c!='\t'&&c!='\n'&&c!='\r'){sb.appendCodePoint(c);c=reader.read();} return sb.toString(); } public String readLine() throws IOException{ StringBuilder sb = new StringBuilder(); while(c!=-1&&c!='\n'&&c!='\r'){sb.appendCodePoint(c);c=reader.read();} return sb.toString(); } public long nextLong() throws IOException, NumberFormatException {return Long.parseLong(nextToken());} public int nextInt() throws NumberFormatException, IOException {return (int) nextLong();} public double nextDouble() throws NumberFormatException, IOException {return Double.parseDouble(nextToken());} }