結果

問題 No.1976 Cut then Connect
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-16 10:31:25
言語 Go
(1.22.1)
結果
AC  
実行時間 240 ms / 2,000 ms
コード長 3,361 bytes
コンパイル時間 10,013 ms
コンパイル使用メモリ 225,256 KB
実行使用メモリ 41,160 KB
最終ジャッジ日時 2024-11-24 12:20:11
合計ジャッジ時間 13,729 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 204 ms
37,384 KB
testcase_03 AC 110 ms
24,920 KB
testcase_04 AC 37 ms
12,188 KB
testcase_05 AC 97 ms
22,776 KB
testcase_06 AC 164 ms
33,300 KB
testcase_07 AC 97 ms
22,852 KB
testcase_08 AC 217 ms
38,608 KB
testcase_09 AC 171 ms
33,976 KB
testcase_10 AC 43 ms
12,308 KB
testcase_11 AC 207 ms
38,240 KB
testcase_12 AC 6 ms
6,820 KB
testcase_13 AC 171 ms
31,172 KB
testcase_14 AC 139 ms
29,132 KB
testcase_15 AC 151 ms
29,588 KB
testcase_16 AC 203 ms
35,832 KB
testcase_17 AC 59 ms
18,640 KB
testcase_18 AC 12 ms
6,820 KB
testcase_19 AC 156 ms
31,844 KB
testcase_20 AC 240 ms
41,160 KB
testcase_21 AC 124 ms
24,868 KB
testcase_22 AC 1 ms
6,816 KB
testcase_23 AC 1 ms
6,816 KB
testcase_24 AC 1 ms
6,820 KB
testcase_25 AC 1 ms
6,820 KB
testcase_26 AC 2 ms
6,820 KB
testcase_27 AC 1 ms
6,820 KB
testcase_28 AC 1 ms
6,820 KB
testcase_29 AC 1 ms
6,820 KB
testcase_30 AC 1 ms
6,820 KB
testcase_31 AC 1 ms
6,820 KB
testcase_32 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {

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

	var n int
	fmt.Fscan(in, &n)

	R := NewRerootingSubtree(n)
	edges := make([][2]int, n-1)
	for i := 0; i < n-1; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		a, b = a-1, b-1
		edges[i] = [2]int{a, b}
		R.AddEdge(a, b, Edge{from: a, to: b, cost: 1})
	}

	// !E: (每个点处的直径,每个点到最远点的距离)
	R.ReRooting(
		func(root int) E { return E{0, 0} },
		func(dp1, dp2 E) E {
			return E{max(max(dp1.dia, dp2.dia), dp1.dist+dp2.dist), max(dp1.dist, dp2.dist)}
		},
		func(dp E, edge Edge) E {
			return E{dp.dia, dp.dist + 1}
		},
	)

	res := n
	for _, e := range edges {
		u, v := e[0], e[1]
		dia1, dia2 := R.SubTree(u, v).dia, R.SubTree(v, u).dia
		res = min(res, max(max(dia1, dia2), (dia1+1)/2+(dia2+1)/2+1))
	}
	fmt.Fprintln(out, res)
}

type E = struct{ dia, dist int }
type Edge = struct{ from, to, cost int }

type Node struct {
	to, rev int
	data    Edge
}

type ReRootingSubtree struct {
	G           [][]Node
	ld, rd      [][]E
	lp, rp      []int
	e           func(root int) E
	op          func(dp1, dp2 E) E
	composition func(dp E, e Edge) E
}

func NewRerootingSubtree(n int) *ReRootingSubtree {
	res := &ReRootingSubtree{
		G:  make([][]Node, n),
		ld: make([][]E, n),
		rd: make([][]E, n),
		lp: make([]int, n),
		rp: make([]int, n),
	}
	return res
}

func (rr *ReRootingSubtree) AddEdge(u, v int, e Edge) {
	rr.G[u] = append(rr.G[u], Node{to: v, data: e})
	rr.G[v] = append(rr.G[v], Node{to: u, data: e})
}

func (rr *ReRootingSubtree) ReRooting(
	e func(root int) E,
	op func(dp1, dp2 E) E,
	composition func(dp E, e Edge) E,
) []E {
	rr.e = e
	rr.op = op
	rr.composition = composition
	n := len(rr.G)
	for i := 0; i < n; i++ {
		sort.Slice(rr.G[i], func(j, k int) bool {
			return rr.G[i][j].to < rr.G[i][k].to
		})
		rr.ld[i] = make([]E, len(rr.G[i])+1)
		rr.rd[i] = make([]E, len(rr.G[i])+1)
		for j := range rr.ld[i] {
			rr.ld[i][j] = e(i)
			rr.rd[i][j] = e(i)
		}
		rr.lp[i] = 0
		rr.rp[i] = len(rr.G[i]) - 1
	}

	for i := 0; i < n; i++ {
		for j := range rr.G[i] {
			rr.G[i][j].rev = rr.search(rr.G[rr.G[i][j].to], i)
		}
	}

	res := make([]E, n)
	for i := 0; i < n; i++ {
		res[i] = rr.dfs(i, -1)
	}
	return res
}

func (rr *ReRootingSubtree) dfs(root, eid int) E {
	for rr.lp[root] != eid && rr.lp[root] < len(rr.G[root]) {
		e := rr.G[root][rr.lp[root]]
		rr.ld[root][rr.lp[root]+1] = rr.op(rr.ld[root][rr.lp[root]], rr.composition(rr.dfs(e.to, e.rev), e.data))
		rr.lp[root]++
	}
	for rr.rp[root] != eid && rr.rp[root] >= 0 {
		e := rr.G[root][rr.rp[root]]
		rr.rd[root][rr.rp[root]] = rr.op(rr.rd[root][rr.rp[root]+1], rr.composition(rr.dfs(e.to, e.rev), e.data))
		rr.rp[root]--
	}
	if eid < 0 {
		return rr.rd[root][0]
	}
	return rr.op(rr.ld[root][eid], rr.rd[root][eid+1])
}

func (rr *ReRootingSubtree) search(vs []Node, idx int) int {
	return sort.Search(len(vs), func(i int) bool { return vs[i].to >= idx })
}

// !root 作为根节点时, 子树 v 的 dp 值
func (rr *ReRootingSubtree) SubTree(root, v int) E {
	k := rr.search(rr.G[root], v)
	return rr.composition(rr.dfs(v, rr.G[root][k].rev), rr.G[root][k].data)
}

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
}
0