#852234 (Go) No.1211 円環はお断り

• 問題: No.1211 円環はお断り
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-24 19:02:08
• 言語: Go (1.22.1)
• 結果: TLE
• 実行時間: -
• コード長: 8,579 bytes
• コンパイル時間: 11,641 ms
• コンパイル使用メモリ: 221,352 KB
• 実行使用メモリ: 167,992 KB
• 最終ジャッジ日時: 2023-10-18 20:34:25
• 合計ジャッジ時間: 46,530 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	1 ms; 4,348 KB
testcase_03	AC	1 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	2 ms; 4,348 KB
testcase_11	AC	2 ms; 4,348 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	1,464 ms; 74,300 KB
testcase_14	TLE	-
testcase_15	AC	1,707 ms; 74,504 KB
testcase_16	TLE	-
testcase_17	AC	164 ms; 16,012 KB
testcase_18	AC	1,369 ms; 67,220 KB
testcase_19	AC	184 ms; 22,660 KB
testcase_20	AC	214 ms; 18,656 KB
testcase_21	AC	240 ms; 22,692 KB
testcase_22	AC	1,359 ms; 85,208 KB
testcase_23	AC	1,976 ms; 100,432 KB
testcase_24	AC	1,135 ms; 58,420 KB
testcase_25	AC	39 ms; 14,416 KB
testcase_26	AC	1,753 ms; 99,568 KB
testcase_27	AC	1,103 ms; 56,772 KB
testcase_28	AC	1,863 ms; 99,244 KB
testcase_29	AC	1,868 ms; 104,352 KB
testcase_30	TLE	-
testcase_31	AC	1,054 ms; 51,072 KB
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-

ソースコード

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	yuki1211()
	// yuki1242()
}

func demo() {
	F := NewFunctionalGraph(6)
	F.AddDirectedEdge(0, 1, 1)
	F.AddDirectedEdge(1, 2, 1)
	F.AddDirectedEdge(2, 3, 1)
	F.AddDirectedEdge(3, 4, 1)
	F.AddDirectedEdge(4, 5, 1)
	F.AddDirectedEdge(5, 0, 1)
	F.Build()
	fmt.Println(F.Jump(0, 7))
}

func yuki1211() {
	// No.1211 円環はお断り
	// https://yukicoder.me/problems/no/1211
	// !给定一个环形数组,分成k个非空连续子数组,使得这k个子数组的和的最小值最大,求出最大值
	// 1<=k<=n<=10^5 1<=nums[i]<=10^9
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, k int
	fmt.Fscan(in, &n, &k)
	nums := make([]int, n, 2*n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums[i])
	}
	nums = append(nums, nums...)
	preSum := make([]int, len(nums)+1)
	for i := 1; i < len(preSum); i++ {
		preSum[i] = preSum[i-1] + nums[i-1]
	}

	// 每段的和是否 >= mid
	check := func(mid int) bool {
		F := NewFunctionalGraph(n + n + 1)
		right := 0
		for left := 0; left < n+n+1; left++ {
			for right < n+n && preSum[right]-preSum[left] < mid {
				right++
			}
			F.AddDirectedEdge(left, right, 1)
		}
		F.Build()
		to := F.JumpAll(k)
		for i := 0; i < n; i++ {
			if to[i] <= i+n {
				return true
			}
		}
		return false
	}
	left, right := 1, preSum[len(preSum)-1]/k+1
	for left <= right {
		mid := (left + right) / 2
		if check(mid) {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	fmt.Fprintln(out, right)
}

func yuki1242() {}

type FunctionalGraph struct {
	G      [][][2]int // (next, weight) 有向图
	Tree   *Tree
	n, m   int
	to     []int
	weight []int
	root   []int
}

func NewFunctionalGraph(n int) *FunctionalGraph {
	fg := &FunctionalGraph{
		n:      n,
		to:     make([]int, n),
		weight: make([]int, n),
		root:   make([]int, n),
	}
	for i := 0; i < n; i++ {
		fg.to[i] = -1
		fg.root[i] = -1
	}
	return fg
}

func (fg *FunctionalGraph) AddDirectedEdge(u, v, w int) {
	fg.m++
	fg.to[u] = v
	fg.weight[u] = w
}

func (fg *FunctionalGraph) Build() {
	n := fg.n
	uf := _NewUF(n)
	for i := 0; i < n; i++ {
		if !uf.Union(i, fg.to[i]) {
			fg.root[i] = i
		}
	}

	for i := 0; i < n; i++ {
		if fg.root[i] == i {
			fg.root[uf.Find(i)] = i
		}
	}

	for i := 0; i < n; i++ {
		fg.root[i] = fg.root[uf.Find(i)]
	}

	g := make([][][2]int, n+1)
	for i := 0; i < n; i++ {
		if fg.root[i] == i {
			g[n] = append(g[n], [2]int{i, fg.weight[i]})
		} else {
			to := fg.to[i]
			g[to] = append(g[to], [2]int{i, fg.weight[i]})
		}
	}

	tree := _NT(g)
	tree.Build(n)

	fg.G = g
	fg.Tree = tree
}

// 从 v 出发，走 step 步，返回到达的点.
func (fg *FunctionalGraph) Jump(v, step int) int {
	d := fg.Tree.Depth[v]
	if step <= d-1 {
		return fg.Tree.Jump(v, fg.n, step)
	}
	v = fg.root[v]
	step -= d - 1
	bottom := fg.to[v]
	c := fg.Tree.Depth[bottom]
	step %= c
	if step == 0 {
		return v
	}
	return fg.Tree.Jump(bottom, fg.n, step-1)
}

// 给定跳跃步数，返回每个节点在该步数内跳跃到的目标节点编号.
func (fg *FunctionalGraph) JumpAll(step int) []int {
	G := fg.Tree.Tree
	res := make([]int, fg.n)
	for i := 0; i < fg.n; i++ {
		res[i] = -1
	}
	query := make([][][2]int, fg.n)
	for v := 0; v < fg.n; v++ {
		d := fg.Tree.Depth[v]
		r := fg.root[v]
		if d-1 > step {
			query[v] = append(query[v], [2]int{v, int(step)})
		} else {
			k := step - (d - 1)
			bottom := fg.to[r]
			c := fg.Tree.Depth[bottom]
			k %= c
			if k == 0 {
				res[v] = r
				continue
			}
			query[bottom] = append(query[bottom], [2]int{v, k - 1})
		}
	}

	path := make([]int, 0)
	var dfs func(v int)
	dfs = func(v int) {
		path = append(path, v)
		for _, q := range query[v] {
			res[q[0]] = path[len(path)-1-q[1]]
		}
		for _, e := range G[v] {
			dfs(e[0])
		}
		path = path[:len(path)-1]
	}
	for _, e := range G[fg.n] {
		dfs(e[0])
	}
	return res
}

// 判断节 v 点是否在 FunctionalGraph 对应的无向图中的环中.
func (fg *FunctionalGraph) IsInCycle(v int) bool {
	return fg.Tree.IsInSubtree(fg.to[fg.root[v]], v)
}

// 给定环的根节点，返回该环上所有节点的编号.
func (fg *FunctionalGraph) CollectCycle(root int) []int {
	cycle := []int{fg.to[root]}
	for cycle[len(cycle)-1] != root {
		cycle = append(cycle, fg.to[cycle[len(cycle)-1]])
	}
	return cycle
}

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

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

type Tree struct {
	Tree          [][][2]int // (next, weight) 有向图
	Depth         []int
	Parent        []int
	LID, RID      []int // 欧拉序[in,out)
	idToNode      []int
	top, heavySon []int
	timer         int
}

func _NT(graph [][][2]int) *Tree {
	n := len(graph)
	lid := make([]int, n)
	rid := make([]int, n)
	idToNode := make([]int, n)
	top := make([]int, n)
	depth := make([]int, n)    // 深度
	parent := make([]int, n)   // 父结点
	heavySon := make([]int, n) // 重儿子
	for i := range parent {
		parent[i] = -1
	}

	return &Tree{
		Tree:     graph, // 有向图
		Depth:    depth,
		Parent:   parent,
		LID:      lid,
		RID:      rid,
		idToNode: idToNode,
		top:      top,
		heavySon: heavySon,
	}
}

// root:0-based
//  当root设为-1时，会从0开始遍历未访问过的连通分量
func (tree *Tree) Build(root int) {
	if root != -1 {
		tree.build(root, -1, 0, 0)
		tree.markTop(root, root)
	} else {
		for i := 0; i < len(tree.Tree); i++ {
			if tree.Parent[i] == -1 {
				tree.build(i, -1, 0, 0)
				tree.markTop(i, i)
			}
		}
	}
}

func (tree *Tree) LCA(u, v int) int {
	for {
		if tree.LID[u] > tree.LID[v] {
			u, v = v, u
		}
		if tree.top[u] == tree.top[v] {
			return u
		}
		v = tree.Parent[tree.top[v]]
	}
}

// k: 0-based
//  如果不存在第k个祖先，返回-1
func (tree *Tree) KthAncestor(root, k int) int {
	if k > tree.Depth[root] {
		return -1
	}
	for {
		u := tree.top[root]
		if tree.LID[root]-k >= tree.LID[u] {
			return tree.idToNode[tree.LID[root]-k]
		}
		k -= tree.LID[root] - tree.LID[u] + 1
		root = tree.Parent[u]
	}
}

// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)
//  返回跳到的节点,如果不存在这样的节点,返回-1
func (tree *Tree) Jump(from, to, step int) int {
	if step == 1 {
		if from == to {
			return -1
		}
		if tree.IsInSubtree(to, from) {
			return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
		}
		return tree.Parent[from]
	}
	c := tree.LCA(from, to)
	dac := tree.Depth[from] - tree.Depth[c]
	dbc := tree.Depth[to] - tree.Depth[c]
	if step > dac+dbc {
		return -1
	}
	if step <= dac {
		return tree.KthAncestor(from, step)
	}
	return tree.KthAncestor(to, dac+dbc-step)
}

// child 是否在 root 的子树中 (child和root不能相等)
func (tree *Tree) IsInSubtree(child, root int) bool {
	return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}

func (tree *Tree) build(cur, pre, dep, dist int) int {
	subSize, heavySize, heavySon := 1, 0, -1
	for _, e := range tree.Tree[cur] { // 有向
		next, weight := e[0], e[1]
		nextSize := tree.build(next, cur, dep+1, dist+weight)
		subSize += nextSize
		if nextSize > heavySize {
			heavySize, heavySon = nextSize, next
		}
	}
	tree.Depth[cur] = dep
	tree.heavySon[cur] = heavySon
	tree.Parent[cur] = pre
	return subSize
}

func (tree *Tree) markTop(cur, top int) {
	tree.top[cur] = top
	tree.LID[cur] = tree.timer
	tree.idToNode[tree.timer] = cur
	tree.timer++
	if tree.heavySon[cur] != -1 {
		tree.markTop(tree.heavySon[cur], top)
		for _, e := range tree.Tree[cur] {
			next := e[0]
			if next != tree.heavySon[cur] { // 有向
				tree.markTop(next, next)
			}
		}
	}
	tree.RID[cur] = tree.timer
}

func _NewUF(n int) *_UF {
	parent, rank := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
		rank[i] = 1
	}

	return &_UF{
		Part:   n,
		rank:   rank,
		n:      n,
		parent: parent,
	}
}

type _UF struct {
	// 连通分量的个数
	Part int

	rank   []int
	n      int
	parent []int
}

func (ufa *_UF) Union(key1, key2 int) bool {
	root1, root2 := ufa.Find(key1), ufa.Find(key2)
	if root1 == root2 {
		return false
	}

	if ufa.rank[root1] > ufa.rank[root2] {
		root1, root2 = root2, root1
	}
	ufa.parent[root1] = root2
	ufa.rank[root2] += ufa.rank[root1]
	ufa.Part--
	return true
}

func (ufa *_UF) Find(key int) int {
	for ufa.parent[key] != key {
		ufa.parent[key] = ufa.parent[ufa.parent[key]]
		key = ufa.parent[key]
	}
	return key
}

func (ufa *_UF) IsConnected(key1, key2 int) bool {
	return ufa.Find(key1) == ufa.Find(key2)
}

func (ufa *_UF) Size(key int) int {
	return ufa.rank[ufa.Find(key)]
}