結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2023-12-28 14:51:00 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 12,706 bytes |
コンパイル時間 | 16,309 ms |
コンパイル使用メモリ | 223,000 KB |
実行使用メモリ | 24,648 KB |
最終ジャッジ日時 | 2024-09-27 15:45:09 |
合計ジャッジ時間 | 31,003 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
package mainimport ("bufio""fmt""os")func main() {yuki1254()}// https://yukicoder.me/problems/no/1254func yuki1254() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)edges := make([]Edge, n)for i := 0; i < n; i++ {var u, v intfmt.Fscan(in, &u, &v)u--v--edges[i] = Edge{u, v, 1}}namori := NewNamoriGraph(n, edges)res := []int{}for i, e := range edges {if namori.InCycle[e[0]] && namori.InCycle[e[1]] {res = append(res, i+1)}}fmt.Fprintln(out, len(res))for _, v := range res {fmt.Fprint(out, v, " ")}}// https://atcoder.jp/contests/abc266/tasks/abc266_ffunc abc266f() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n intfmt.Fscan(in, &n)}func demo() {edges := []Edge{{0, 1, 1}, {1, 2, 2}, {1, 3, 3}, {2, 6, 6}, {3, 6, 6}, {3, 4, 4}, {4, 5, 5},}namori := NewNamoriGraph(7, edges)fmt.Println(namori.Root)fmt.Println(namori.OutEdgeId)fmt.Println(namori.OutCost)fmt.Println(namori.To)fmt.Println(namori.Cycle)directedGraph, tree := namori.BuildTree()fmt.Println(directedGraph)fmt.Println(namori.Dist(tree, 0, 5))}type Edge = [3]int // (u,v,w)type Neighbor = struct{ to, weight, eid int }// !无向基环树.type NamoriGraph struct {RawEdges []EdgeRawGraph [][]NeighborN intRoot int // 断开outEdge后有向树的根OutEdgeId int // build后不在树中的边OutCost intTo []int // !向Root方向移动1步后的结点,Root的To为对应outEdge的另一端Cycle []intInCycle []bool}func NewNamoriGraph(n int, edges []Edge) *NamoriGraph {m := len(edges)if m != n {panic("invalid namori graph")}graph := make([][]Neighbor, n)for eid := 0; eid < m; eid++ {e := &edges[eid]u, v, w := e[0], e[1], e[2]graph[u] = append(graph[u], Neighbor{to: v, weight: w, eid: eid})graph[v] = append(graph[v], Neighbor{to: u, weight: w, eid: eid})}uf := NewUf(n)to := make([]int, n)for i := range to {to[i] = -1}root := -1outEdgeId, outCost := -1, -1for eid := 0; eid < m; eid++ {e := &edges[eid]u, v, w := e[0], e[1], e[2]if uf.Union(u, v) {continue}outEdgeId, outCost = eid, wroot = uto[root] = vbreak}visited := make([]bool, n)stack := []int{root}for len(stack) > 0 {pre := stack[len(stack)-1]stack = stack[:len(stack)-1]visited[pre] = truefor _, e := range graph[pre] {next, eid := e.to, e.eidif visited[next] || eid == outEdgeId {continue}to[next] = prestack = append(stack, next)}}cycle := []int{to[root]}for cycle[len(cycle)-1] != root {cycle = append(cycle, to[cycle[len(cycle)-1]])}inCycle := make([]bool, n)for _, v := range cycle {inCycle[v] = true}return &NamoriGraph{RawEdges: edges,RawGraph: graph,N: n,Root: root,OutEdgeId: outEdgeId,OutCost: outCost,To: to,Cycle: cycle,InCycle: inCycle,}}// 断开outEdge, 生成有向树.func (ng *NamoriGraph) BuildTree() (directedGraph [][]Neighbor, tree *Tree) {directedGraph = make([][]Neighbor, ng.N)for eid := 0; eid < ng.N; eid++ {if eid == ng.OutEdgeId {continue}e := &ng.RawEdges[eid]u, v, w := e[0], e[1], e[2]if ng.To[u] == v {u, v = v, u}directedGraph[u] = append(directedGraph[u], Neighbor{to: v, weight: w, eid: eid})}tree = NewTree(directedGraph, ng.Root)return}func (ng *NamoriGraph) Dist(tree *Tree, u, v int) int {bottom := ng.To[ng.Root]lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)diff := abs(tree.Depth[lca1] - tree.Depth[lca2])diff = min(diff, len(ng.Cycle)-diff)return diff + tree.Depth[u] + tree.Depth[v] - tree.Depth[lca1] - tree.Depth[lca2]}func (ng *NamoriGraph) DistWeighted(tree *Tree, u, v int) int {bottom := ng.To[ng.Root]lca1, lca2 := tree.LCA(u, bottom), tree.LCA(v, bottom)diff := abs(tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2])diff = min(diff, tree.DepthWeighted[bottom]+ng.OutCost-diff)return diff + tree.DepthWeighted[u] + tree.DepthWeighted[v] - tree.DepthWeighted[lca1] - tree.DepthWeighted[lca2]}type Uf struct {data []int}func NewUf(n int) *Uf {data := make([]int, n)for i := 0; i < n; i++ {data[i] = -1}return &Uf{data: data}}func (ufa *Uf) Union(key1, key2 int) bool {root1, root2 := ufa.Find(key1), ufa.Find(key2)if root1 == root2 {return false}if ufa.data[root1] > ufa.data[root2] {root1, root2 = root2, root1}ufa.data[root1] += ufa.data[root2]ufa.data[root2] = root1return true}func (ufa *Uf) Find(key int) int {if ufa.data[key] < 0 {return key}ufa.data[key] = ufa.Find(ufa.data[key])return ufa.data[key]}type Tree struct {Tree [][]NeighborDepth, DepthWeighted []intParent []intLID, RID []int // 欧拉序[in,out)IdToNode []inttop, heavySon []inttimer int}func NewTree(adjList [][]Neighbor, root int) *Tree {n := len(adjList)lid := make([]int, n)rid := make([]int, n)idToNode := make([]int, n)top := make([]int, n) // 所处轻/重链的顶点(深度最小),轻链的顶点为自身depth := make([]int, n) // 深度depthWeighted := make([]int, n)parent := make([]int, n) // 父结点heavySon := make([]int, n) // 重儿子for i := range parent {parent[i] = -1}res := &Tree{Tree: adjList,Depth: depth,DepthWeighted: depthWeighted,Parent: parent,LID: lid,RID: rid,IdToNode: idToNode,top: top,heavySon: heavySon,}res.Build(root)return res}// 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)}}}}// 返回 root 的欧拉序区间, 左闭右开, 0-indexed.func (tree *Tree) Id(root int) (int, int) {return tree.LID[root], tree.RID[root]}// 返回返回边 u-v 对应的 欧拉序起点编号, 1 <= eid <= n-1., 0-indexed.func (tree *Tree) Eid(u, v int) int {if tree.LID[u] > tree.LID[v] {return tree.LID[u]}return tree.LID[v]}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]]}}func (tree *Tree) RootedLCA(u, v int, root int) int {return tree.LCA(u, v) ^ tree.LCA(u, root) ^ tree.LCA(v, root)}func (tree *Tree) RootedParent(u int, root int) int {return tree.Jump(u, root, 1)}func (tree *Tree) Dist(u, v int, weighted bool) int {if weighted {return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]}return tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)]}// k: 0-based//// 如果不存在第k个祖先,返回-1// kthAncestor(root,0) == rootfunc (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] + 1root = tree.Parent[u]}}// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)//// 返回跳到的节点,如果不存在这样的节点,返回-1func (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)}func (tree *Tree) CollectChild(root int) []int {res := []int{}for _, e := range tree.Tree[root] {next := e.toif next != tree.Parent[root] {res = append(res, next)}}return res}// 返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.//// !eg:[[2 0] [4 4]] 沿着路径顺序但不一定沿着欧拉序.func (tree *Tree) GetPathDecomposition(u, v int, vertex bool) [][2]int {up, down := [][2]int{}, [][2]int{}for {if tree.top[u] == tree.top[v] {break}if tree.LID[u] < tree.LID[v] {down = append(down, [2]int{tree.LID[tree.top[v]], tree.LID[v]})v = tree.Parent[tree.top[v]]} else {up = append(up, [2]int{tree.LID[u], tree.LID[tree.top[u]]})u = tree.Parent[tree.top[u]]}}edgeInt := 1if vertex {edgeInt = 0}if tree.LID[u] < tree.LID[v] {down = append(down, [2]int{tree.LID[u] + edgeInt, tree.LID[v]})} else if tree.LID[v]+edgeInt <= tree.LID[u] {up = append(up, [2]int{tree.LID[u], tree.LID[v] + edgeInt})}for i := 0; i < len(down)/2; i++ {down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]}return append(up, down...)}// 遍历路径上的 `[起点,终点)` 欧拉序 `左闭右开` 区间.func (tree *Tree) EnumeratePathDecomposition(u, v int, vertex bool, f func(start, end int)) {for {if tree.top[u] == tree.top[v] {break}if tree.LID[u] < tree.LID[v] {a, b := tree.LID[tree.top[v]], tree.LID[v]if a > b {a, b = b, a}f(a, b+1)v = tree.Parent[tree.top[v]]} else {a, b := tree.LID[u], tree.LID[tree.top[u]]if a > b {a, b = b, a}f(a, b+1)u = tree.Parent[tree.top[u]]}}edgeInt := 1if vertex {edgeInt = 0}if tree.LID[u] < tree.LID[v] {a, b := tree.LID[u]+edgeInt, tree.LID[v]if a > b {a, b = b, a}f(a, b+1)} else if tree.LID[v]+edgeInt <= tree.LID[u] {a, b := tree.LID[u], tree.LID[v]+edgeIntif a > b {a, b = b, a}f(a, b+1)}}func (tree *Tree) GetPath(u, v int) []int {res := []int{}composition := tree.GetPathDecomposition(u, v, true)for _, e := range composition {a, b := e[0], e[1]if a <= b {for i := a; i <= b; i++ {res = append(res, tree.IdToNode[i])}} else {for i := a; i >= b; i-- {res = append(res, tree.IdToNode[i])}}}return res}// 以root为根时,结点v的子树大小.func (tree *Tree) SubSize(v, root int) int {if root == -1 {return tree.RID[v] - tree.LID[v]}if v == root {return len(tree.Tree)}x := tree.Jump(v, root, 1)if tree.IsInSubtree(v, x) {return tree.RID[v] - tree.LID[v]}return len(tree.Tree) - tree.RID[x] + tree.LID[x]}// 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]}// 寻找以 start 为 top 的重链 ,heavyPath[-1] 即为重链底端节点.func (tree *Tree) GetHeavyPath(start int) []int {heavyPath := []int{start}cur := startfor tree.heavySon[cur] != -1 {cur = tree.heavySon[cur]heavyPath = append(heavyPath, cur)}return heavyPath}// 结点v的重儿子.如果没有重儿子,返回-1.func (tree *Tree) GetHeavyChild(v int) int {k := tree.LID[v] + 1if k == len(tree.Tree) {return -1}w := tree.IdToNode[k]if tree.Parent[w] == v {return w}return -1}func (tree *Tree) ELID(u int) int {return 2*tree.LID[u] - tree.Depth[u]}func (tree *Tree) ERID(u int) int {return 2*tree.RID[u] - tree.Depth[u] - 1}func (tree *Tree) build(cur, pre, dep, dist int) int {subSize, heavySize, heavySon := 1, 0, -1for _, e := range tree.Tree[cur] {next, weight := e.to, e.weightif next != pre {nextSize := tree.build(next, cur, dep+1, dist+weight)subSize += nextSizeif nextSize > heavySize {heavySize, heavySon = nextSize, next}}}tree.Depth[cur] = deptree.DepthWeighted[cur] = disttree.heavySon[cur] = heavySontree.Parent[cur] = prereturn subSize}func (tree *Tree) markTop(cur, top int) {tree.top[cur] = toptree.LID[cur] = tree.timertree.IdToNode[tree.timer] = curtree.timer++heavySon := tree.heavySon[cur]if heavySon != -1 {tree.markTop(heavySon, top)for _, e := range tree.Tree[cur] {next := e.toif next != heavySon && next != tree.Parent[cur] {tree.markTop(next, next)}}}tree.RID[cur] = tree.timer}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}func abs(a int) int {if a < 0 {return -a}return a}