結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー 草苺奶昔
提出日時 2023-03-14 19:08:00
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,861 bytes
コンパイル時間 12,431 ms
コンパイル使用メモリ 232,200 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 08:22:28
合計ジャッジ時間 10,645 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var w int
	fmt.Fscan(in, &w)
	var n int
	fmt.Fscan(in, &n)
	A := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &A[i])
	}
	var m int
	fmt.Fscan(in, &m)
	B := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(in, &B[i])
	}

	ok := make([][]bool, m)
	for i := 0; i < m; i++ {
		ok[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			ok[i][j] = true
		}
	}

	for i := 0; i < m; i++ {
		var q int
		fmt.Fscan(in, &q)
		for j := 0; j < q; j++ {
			var x int
			fmt.Fscan(in, &x)
			ok[i][x-1] = false
		}
	}

	res := 制作進行の宮森あおいです(w, A, B, ok)
	if res {
		fmt.Fprintln(out, "SHIROBAKO")
	} else {
		fmt.Fprintln(out, "BANSAKUTSUKITA")
	}
}

func 制作進行の宮森あおいです(w int, A, B []int, ok [][]bool) bool {
	n, m := len(A), len(B)
	S, T := n+m, n+m+1
	flow := NewPushRelabel(n + m + 2)

	left := func(i int) int { return i }
	right := func(i int) int { return i + n }

	for i := 0; i < n; i++ {
		flow.AddEdge(S, left(i), A[i])
	}
	for i := 0; i < m; i++ {
		flow.AddEdge(right(i), T, B[i])
	}

	for j := 0; j < m; j++ {
		for i := 0; i < n; i++ {
			if ok[j][i] {
				flow.AddEdge(left(i), right(j), INF)
			}
		}
	}

	return flow.MaxFlow(S, T) >= w
}

const INF int = 1e18

type edge struct{ to, rid, cap int }

type PushRelabel struct {
	graph [][]edge
}

func NewPushRelabel(n int) *PushRelabel {
	return &PushRelabel{
		graph: make([][]edge, n),
	}
}

func (pr *PushRelabel) AddEdge(from, to, cap int) {
	pr.graph[from] = append(pr.graph[from], edge{to, len(pr.graph[to]), cap})
	pr.graph[to] = append(pr.graph[to], edge{from, len(pr.graph[from]) - 1, 0})
}

func (pr *PushRelabel) MaxFlow(s, t int) int {
	n := len(pr.graph)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = -1
	}

	dist[t] = 0
	cd := make([]int, 2*n)
	queue := []int{t}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		cd[dist[v]]++
		for _, e := range pr.graph[v] {
			if w := e.to; dist[w] < 0 {
				dist[w] = dist[v] + 1
				queue = append(queue, w)
			}
		}
	}
	dist[s] = n

	exFlow := make([]int, n)
	pq := hp{d: dist}
	inQueue := make([]bool, n)
	push := func(v, f int, e *edge) {
		w := e.to
		e.cap -= f
		pr.graph[w][e.rid].cap += f
		exFlow[v] -= f
		exFlow[w] += f
		if w != s && w != t && !inQueue[w] {
			pq.push(w)
			inQueue[w] = true
		}
	}

	for i := range pr.graph[s] {
		if e := &pr.graph[s][i]; e.cap > 0 {
			push(s, e.cap, e)
		}
	}

	for pq.Len() > 0 {
		v := pq.pop()
		inQueue[v] = false
	o:
		for {
			for i := range pr.graph[v] {
				if e := &pr.graph[v][i]; e.cap > 0 && dist[e.to] < dist[v] {
					push(v, min(e.cap, exFlow[v]), e)
					if exFlow[v] == 0 {
						break o
					}
				}
			}
			dv := dist[v]
			if dv != -1 {
				if cd[dv]--; cd[dv] == 0 {
					for i, h := range dist {
						if i != s && i != t && dv < h && h <= n {
							dist[i] = n + 1
						}
					}
				}
			}
			minD := INF
			for _, e := range pr.graph[v] {
				if w := e.to; e.cap > 0 && dist[w] < minD {
					minD = dist[w]
				}
			}
			dist[v] = minD + 1
			cd[dist[v]]++
		}
	}

	return exFlow[t]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type hp struct{ vs, d []int }

func (h hp) Len() int              { return len(h.vs) }
func (h hp) Less(i, j int) bool    { return h.d[h.vs[i]] > h.d[h.vs[j]] }
func (h hp) Swap(i, j int)         { h.vs[i], h.vs[j] = h.vs[j], h.vs[i] }
func (h *hp) Push(v interface{})   { h.vs = append(h.vs, v.(int)) }
func (h *hp) Pop() (v interface{}) { a := h.vs; h.vs, v = a[:len(a)-1], a[len(a)-1]; return }
func (h *hp) push(v int)           { heap.Push(h, v) }
func (h *hp) pop() int             { return heap.Pop(h).(int) }
0