結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2015-04-03 00:12:19 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 7,622 bytes |
コンパイル時間 | 4,349 ms |
コンパイル使用メモリ | 81,220 KB |
実行使用メモリ | 37,308 KB |
最終ジャッジ日時 | 2024-07-04 01:29:10 |
合計ジャッジ時間 | 5,027 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
import java.util.*;import java.io.*;import static java.util.Arrays.*;import static java.lang.Math.*;public class No177 {static final InputStream in = System.in;static final PrintWriter out = new PrintWriter(System.out,false);@SuppressWarnings("unchecked")static void solve(){int w = nextInt();int n = nextInt();ArrayList[] list = new ArrayList[3];for (int i=0; i<3; i++) list[i] = new ArrayList<Integer>();int[] x = new int[n+1];for (int i=0; i<n; i++) {list[0].add(0);list[1].add(i+1);int t = nextInt();list[2].add(t);x[i+1] = t;}int m = nextInt();for (int i=0; i<m; i++) {list[0].add(n+i+1);list[1].add(n+m+1);list[2].add(nextInt());}for (int i=0; i<m; i++) {int q = nextInt();boolean[] f = new boolean[n+1];for (int j=0; j<q; j++) {f[nextInt()] = true;}for (int j=1; j<=n; j++) {if (f[j]) continue;list[0].add(j);list[1].add(n+i+1);list[2].add(x[j]);}}int[][][] g = toAdjacencyList(n+m+2,list);out.println(w <= dinic(g,0,n+m+1) ? "SHIROBAKO" : "BANSAKUTSUKITA");}static int[][][] toAdjacencyList(int n,ArrayList<Integer>[] list) {int[] cnt = new int[n];for (int i : list[0]) cnt[i]++;for (int i : list[1]) cnt[i]++;int[][][] g = new int[n][][];for (int i=0; i<n; i++) g[i] = new int[cnt[i]][2];for (int i=0; i<list[0].size(); i++) {int f = list[0].get(i);int t = list[1].get(i);g[f][--cnt[f]][0] = t;g[f][cnt[f]][1] = list[2].get(i);}return g;}static int dinic(int[][][] g, int source, int sink) {int n = g.length;int[] cnt = new int[n];for (int i=0; i<n; i++)for (int j=0; j<g[i].length; j++)cnt[g[i][j][0]]++;int[][] rev = new int[n][];for (int i=0; i<n; i++) rev[i] = new int[cnt[i]];for (int i=n-1; i>=0; i--)for (int j=0; j<g[i].length; j++)rev[g[i][j][0]][--cnt[g[i][j][0]]] = i;int[][] flow = new int[n][n];int[] level = new int[n];int[] path = new int[n];int ret = 0;while (true) {fill(level,-1);path[0] = source;int ptr = 1;level[source] = 0;for (int i=0; i<ptr; i++) {int cur = path[i];for (int[] edge : g[cur]) {int next = edge[0], cap = edge[1];if (level[next] == -1 && cap - flow[cur][next] > 0) {path[ptr++] = next;level[next] = level[cur] + 1;}}for (int next : rev[cur]) {if (level[next] == -1 && -flow[cur][next] > 0) {path[ptr++] = next;level[next] = level[cur] + 1;}}}if (level[sink] == -1) break;int f = 0;while ((f = dfsDinic(g,level,rev,flow,source,sink,Integer.MAX_VALUE/2)) > 0)ret += f;}return ret;}static int dfsDinic(int[][][] g, int[] level, int[][] rev, int[][] flow, int cur, int sink, int min){if (cur == sink) return min;int left = min;for (int[] edge : g[cur]) {int next = edge[0], cap = edge[1];if (level[next] == level[cur] + 1 && cap-flow[cur][next] > 0) {int f = dfsDinic(g,level,rev,flow,next,sink,min(left, cap-flow[cur][next]));if (f > 0) {flow[cur][next] += f;flow[next][cur] -= f;left -= f;if (left == 0) return min;}}}for (int next : rev[cur]) {if (level[next] == level[cur] + 1 && -flow[cur][next] > 0) {int f = dfsDinic(g,level,rev,flow,next,sink,min(left, -flow[cur][next]));if (f > 0) {flow[cur][next] += f;flow[next][cur] -= f;left -= f;if (left == 0) return min;}}}return min - left;}public static void main(String[] args) throws Exception {long start = System.currentTimeMillis();solve();out.flush();long end = System.currentTimeMillis();//trace(end-start + "ms");in.close();}static void trace(Object... o) { System.out.println(deepToString(o));}static final byte[] buf = new byte[1024];static int ptr = 0;static int buflen = 0;static boolean hasNextByte() {if (ptr < buflen)return true;ptr = 0;try{buflen = in.read(buf);}catch (IOException e) {e.printStackTrace();}if (buflen <= 0)return false;return true;}static int readByte() { if (hasNextByte()) return buf[ptr++]; else return -1;}static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}static void skip() { while(hasNextByte() && !isPrintableChar(buf[ptr])) ptr++;}static boolean hasNext() {skip(); return hasNextByte();}static String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}static long nextLong() {if (!hasNext()) throw new NoSuchElementException();boolean minus = false;long num = readByte();if(num == '-'){num = 0;minus = true;}else if (num < '0' || '9' < num){throw new NumberFormatException();}else{num -= '0';}while(true){int b = readByte();if('0' <= b && b <= '9')num = num * 10 + (b - '0');else if(b == -1 || !isPrintableChar(b))return minus ? -num : num;elsethrow new NoSuchElementException();}}static int nextInt() {long num = nextLong();if (num < Integer.MIN_VALUE || Integer.MAX_VALUE < num)throw new NumberFormatException();return (int)num;}static double nextDouble() {return Double.parseDouble(next());}static char nextChar() {if (!hasNext()) throw new NoSuchElementException();return (char)readByte();}static String nextLine() {while (hasNextByte() && (buf[ptr] == '\n' || buf[ptr] == '\r')) ptr++;if (!hasNextByte()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (b != '\n' && b != '\r') {sb.appendCodePoint(b);b = readByte();}return sb.toString();}static int[] nextArrayInt(int n) {int[] a = new int[n];for (int i=0; i<n; i++) a[i] = nextInt();return a;}}