結果
問題 | No.1254 補強への架け橋 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-24 15:20:36 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 259 ms / 2,000 ms |
コード長 | 3,951 bytes |
コンパイル時間 | 11,397 ms |
コンパイル使用メモリ | 207,832 KB |
実行使用メモリ | 45,920 KB |
最終ジャッジ日時 | 2023-10-18 20:29:20 |
合計ジャッジ時間 | 28,190 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 1 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 1 ms
4,348 KB |
testcase_13 | AC | 1 ms
4,348 KB |
testcase_14 | AC | 1 ms
4,348 KB |
testcase_15 | AC | 1 ms
4,348 KB |
testcase_16 | AC | 1 ms
4,348 KB |
testcase_17 | AC | 1 ms
4,348 KB |
testcase_18 | AC | 1 ms
4,348 KB |
testcase_19 | AC | 1 ms
4,348 KB |
testcase_20 | AC | 1 ms
4,348 KB |
testcase_21 | AC | 1 ms
4,348 KB |
testcase_22 | AC | 1 ms
4,348 KB |
testcase_23 | AC | 2 ms
4,348 KB |
testcase_24 | AC | 1 ms
4,348 KB |
testcase_25 | AC | 1 ms
4,348 KB |
testcase_26 | AC | 1 ms
4,348 KB |
testcase_27 | AC | 2 ms
4,348 KB |
testcase_28 | AC | 1 ms
4,348 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 1 ms
4,348 KB |
testcase_31 | AC | 2 ms
4,348 KB |
testcase_32 | AC | 2 ms
4,348 KB |
testcase_33 | AC | 2 ms
4,348 KB |
testcase_34 | AC | 2 ms
4,348 KB |
testcase_35 | AC | 1 ms
4,348 KB |
testcase_36 | AC | 1 ms
4,348 KB |
testcase_37 | AC | 1 ms
4,348 KB |
testcase_38 | AC | 2 ms
4,348 KB |
testcase_39 | AC | 1 ms
4,348 KB |
testcase_40 | AC | 1 ms
4,348 KB |
testcase_41 | AC | 2 ms
4,348 KB |
testcase_42 | AC | 1 ms
4,348 KB |
testcase_43 | AC | 2 ms
4,348 KB |
testcase_44 | AC | 2 ms
4,348 KB |
testcase_45 | AC | 2 ms
4,348 KB |
testcase_46 | AC | 2 ms
4,348 KB |
testcase_47 | AC | 2 ms
4,348 KB |
testcase_48 | AC | 2 ms
4,348 KB |
testcase_49 | AC | 1 ms
4,348 KB |
testcase_50 | AC | 2 ms
4,348 KB |
testcase_51 | AC | 2 ms
4,348 KB |
testcase_52 | AC | 2 ms
4,348 KB |
testcase_53 | AC | 2 ms
4,348 KB |
testcase_54 | AC | 2 ms
4,348 KB |
testcase_55 | AC | 3 ms
4,348 KB |
testcase_56 | AC | 1 ms
4,348 KB |
testcase_57 | AC | 2 ms
4,348 KB |
testcase_58 | AC | 2 ms
4,348 KB |
testcase_59 | AC | 2 ms
4,348 KB |
testcase_60 | AC | 2 ms
4,348 KB |
testcase_61 | AC | 2 ms
4,348 KB |
testcase_62 | AC | 1 ms
4,348 KB |
testcase_63 | AC | 15 ms
7,800 KB |
testcase_64 | AC | 4 ms
4,348 KB |
testcase_65 | AC | 9 ms
5,692 KB |
testcase_66 | AC | 8 ms
5,676 KB |
testcase_67 | AC | 3 ms
4,348 KB |
testcase_68 | AC | 9 ms
4,376 KB |
testcase_69 | AC | 11 ms
5,716 KB |
testcase_70 | AC | 5 ms
4,348 KB |
testcase_71 | AC | 4 ms
4,348 KB |
testcase_72 | AC | 11 ms
5,720 KB |
testcase_73 | AC | 5 ms
4,348 KB |
testcase_74 | AC | 10 ms
5,712 KB |
testcase_75 | AC | 8 ms
5,676 KB |
testcase_76 | AC | 3 ms
4,348 KB |
testcase_77 | AC | 7 ms
5,672 KB |
testcase_78 | AC | 14 ms
7,772 KB |
testcase_79 | AC | 14 ms
7,784 KB |
testcase_80 | AC | 12 ms
5,724 KB |
testcase_81 | AC | 14 ms
7,800 KB |
testcase_82 | AC | 12 ms
5,708 KB |
testcase_83 | AC | 182 ms
27,400 KB |
testcase_84 | AC | 178 ms
27,436 KB |
testcase_85 | AC | 103 ms
18,848 KB |
testcase_86 | AC | 151 ms
25,276 KB |
testcase_87 | AC | 173 ms
25,356 KB |
testcase_88 | AC | 22 ms
8,024 KB |
testcase_89 | AC | 186 ms
27,256 KB |
testcase_90 | AC | 111 ms
21,004 KB |
testcase_91 | AC | 87 ms
15,904 KB |
testcase_92 | AC | 42 ms
10,368 KB |
testcase_93 | AC | 144 ms
25,244 KB |
testcase_94 | AC | 129 ms
23,016 KB |
testcase_95 | AC | 135 ms
23,000 KB |
testcase_96 | AC | 176 ms
25,204 KB |
testcase_97 | AC | 72 ms
14,792 KB |
testcase_98 | AC | 178 ms
27,384 KB |
testcase_99 | AC | 98 ms
18,916 KB |
testcase_100 | AC | 192 ms
27,432 KB |
testcase_101 | AC | 37 ms
10,372 KB |
testcase_102 | AC | 20 ms
6,932 KB |
testcase_103 | AC | 41 ms
10,416 KB |
testcase_104 | AC | 59 ms
11,656 KB |
testcase_105 | AC | 140 ms
25,256 KB |
testcase_106 | AC | 81 ms
16,760 KB |
testcase_107 | AC | 189 ms
27,464 KB |
testcase_108 | AC | 184 ms
27,196 KB |
testcase_109 | AC | 138 ms
23,180 KB |
testcase_110 | AC | 124 ms
20,692 KB |
testcase_111 | AC | 133 ms
23,152 KB |
testcase_112 | AC | 56 ms
12,464 KB |
testcase_113 | AC | 118 ms
21,044 KB |
testcase_114 | AC | 75 ms
14,644 KB |
testcase_115 | AC | 25 ms
8,064 KB |
testcase_116 | AC | 89 ms
16,792 KB |
testcase_117 | AC | 55 ms
12,496 KB |
testcase_118 | AC | 171 ms
25,312 KB |
testcase_119 | AC | 96 ms
16,808 KB |
testcase_120 | AC | 170 ms
27,336 KB |
testcase_121 | AC | 48 ms
10,388 KB |
testcase_122 | AC | 89 ms
15,548 KB |
testcase_123 | AC | 1 ms
4,348 KB |
testcase_124 | AC | 259 ms
45,920 KB |
testcase_125 | AC | 259 ms
45,900 KB |
ソースコード
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) g := make([][]Edge, n) for i := 0; i < n; i++ { var a, b int fmt.Fscan(in, &a, &b) a-- b-- g[a] = append(g[a], Edge{a, b, 1, i}) g[b] = append(g[b], Edge{b, a, 1, i}) } ng := NewNamoriGraph(g) ng.Build() res := []int{} for _, e := range ng.CycleEdges { res = append(res, e.id+1) } sort.Ints(res) fmt.Fprintln(out, len(res)) for _, v := range res { fmt.Fprint(out, v, " ") } } type NamoriGraph struct { // !以环上各个顶点i为根的无向树 Trees []Graph // !基环树中在环上的边,边i连接着树的 root i和i+1 (i>=0) CycleEdges []Edge g Graph iv [][]int markId, id []int } type Edge = struct{ from, to, cost, id int } type Graph = [][]Edge func NewNamoriGraph(g Graph) *NamoriGraph { return &NamoriGraph{g: g} } func (ng *NamoriGraph) Build() { n := len(ng.g) deg := make([]int, n) used := make([]bool, n) que := []int{} for i := 0; i < n; i++ { deg[i] = len(ng.g[i]) if deg[i] == 1 { que = append(que, i) used[i] = true } } for len(que) > 0 { idx := que[0] que = que[1:] for _, e := range ng.g[idx] { if used[e.to] { continue } deg[e.to]-- if deg[e.to] == 1 { que = append(que, e.to) used[e.to] = true } } } mx := 0 for _, edges := range ng.g { for _, e := range edges { mx = max(mx, e.id) } } edgeUsed := make([]bool, mx+1) loop := []int{} for i := 0; i < n; i++ { if used[i] { continue } for update := true; update; { update = false loop = append(loop, i) for _, e := range ng.g[i] { if used[e.to] || edgeUsed[e.id] { continue } edgeUsed[e.id] = true ng.CycleEdges = append(ng.CycleEdges, Edge{i, e.to, e.cost, e.id}) i = e.to update = true break } } break } loop = loop[:len(loop)-1] ng.markId = make([]int, n) ng.id = make([]int, n) for i := 0; i < len(loop); i++ { pre := loop[(i+len(loop)-1)%len(loop)] nxt := loop[(i+1)%len(loop)] sz := 0 ng.markId[loop[i]] = i ng.iv = append(ng.iv, []int{}) ng.id[loop[i]] = sz sz++ ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], loop[i]) for _, e := range ng.g[loop[i]] { if e.to != pre && e.to != nxt { ng.markDfs(e.to, loop[i], i, &sz) } } tree := make(Graph, sz) for _, e := range ng.g[loop[i]] { if e.to != pre && e.to != nxt { tree[ng.id[loop[i]]] = append(tree[ng.id[loop[i]]], Edge{ng.id[loop[i]], ng.id[e.to], e.cost, e.id}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[loop[i]], e.cost, e.id}) ng.buildDfs(e.to, loop[i], tree) } } ng.Trees = append(ng.Trees, tree) } } // 给定原图的顶点rawV,返回rawV所在的树的根节点和rawV在树中的编号. func (ng *NamoriGraph) GetId(rawV int) (rootId, idInTree int) { return ng.markId[rawV], ng.id[rawV] } // 给定树的顶点编号root和某个点在树中的顶点编号idInTree,返回这个点在原图中的顶点编号. // GetInvId(root,0) 表示在环上的顶点root在原图中对应的顶点. func (ng *NamoriGraph) GetInvId(rootId, idInTree int) (rawV int) { return ng.iv[rootId][idInTree] } func (ng *NamoriGraph) markDfs(idx, par, k int, l *int) { ng.markId[idx] = k ng.id[idx] = *l *l++ ng.iv[len(ng.iv)-1] = append(ng.iv[len(ng.iv)-1], idx) for _, e := range ng.g[idx] { if e.to != par { ng.markDfs(e.to, idx, k, l) } } } func (ng *NamoriGraph) buildDfs(idx, par int, tree Graph) { for _, e := range ng.g[idx] { if e.to != par { tree[ng.id[idx]] = append(tree[ng.id[idx]], Edge{ng.id[idx], ng.id[e.to], e.cost, e.id}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[idx], e.cost, e.id}) ng.buildDfs(e.to, idx, tree) } } } func max(a, b int) int { if a > b { return a } return b }