結果
問題 | No.1254 補強への架け橋 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-13 02:24:05 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 262 ms / 2,000 ms |
コード長 | 4,215 bytes |
コンパイル時間 | 13,997 ms |
コンパイル使用メモリ | 197,768 KB |
実行使用メモリ | 47,980 KB |
最終ジャッジ日時 | 2023-09-23 08:31:05 |
合計ジャッジ時間 | 30,921 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 1 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 1 ms
4,376 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,376 KB |
testcase_31 | AC | 1 ms
4,376 KB |
testcase_32 | AC | 1 ms
4,376 KB |
testcase_33 | AC | 1 ms
4,376 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 1 ms
4,376 KB |
testcase_38 | AC | 2 ms
4,376 KB |
testcase_39 | AC | 2 ms
4,376 KB |
testcase_40 | AC | 2 ms
4,376 KB |
testcase_41 | AC | 1 ms
4,376 KB |
testcase_42 | AC | 2 ms
4,376 KB |
testcase_43 | AC | 2 ms
4,376 KB |
testcase_44 | AC | 2 ms
4,376 KB |
testcase_45 | AC | 2 ms
4,380 KB |
testcase_46 | AC | 2 ms
4,380 KB |
testcase_47 | AC | 2 ms
4,380 KB |
testcase_48 | AC | 2 ms
4,380 KB |
testcase_49 | AC | 2 ms
4,376 KB |
testcase_50 | AC | 2 ms
4,376 KB |
testcase_51 | AC | 3 ms
4,376 KB |
testcase_52 | AC | 2 ms
4,380 KB |
testcase_53 | AC | 2 ms
4,376 KB |
testcase_54 | AC | 3 ms
4,376 KB |
testcase_55 | AC | 2 ms
4,380 KB |
testcase_56 | AC | 1 ms
4,380 KB |
testcase_57 | AC | 2 ms
4,376 KB |
testcase_58 | AC | 2 ms
4,380 KB |
testcase_59 | AC | 1 ms
4,376 KB |
testcase_60 | AC | 2 ms
4,376 KB |
testcase_61 | AC | 2 ms
4,376 KB |
testcase_62 | AC | 1 ms
4,376 KB |
testcase_63 | AC | 16 ms
7,840 KB |
testcase_64 | AC | 4 ms
4,376 KB |
testcase_65 | AC | 10 ms
5,748 KB |
testcase_66 | AC | 8 ms
5,728 KB |
testcase_67 | AC | 4 ms
4,376 KB |
testcase_68 | AC | 9 ms
4,400 KB |
testcase_69 | AC | 11 ms
5,776 KB |
testcase_70 | AC | 6 ms
4,376 KB |
testcase_71 | AC | 4 ms
4,380 KB |
testcase_72 | AC | 11 ms
5,764 KB |
testcase_73 | AC | 5 ms
4,380 KB |
testcase_74 | AC | 10 ms
5,760 KB |
testcase_75 | AC | 8 ms
5,728 KB |
testcase_76 | AC | 3 ms
4,376 KB |
testcase_77 | AC | 8 ms
5,728 KB |
testcase_78 | AC | 14 ms
5,760 KB |
testcase_79 | AC | 15 ms
5,916 KB |
testcase_80 | AC | 13 ms
5,780 KB |
testcase_81 | AC | 15 ms
7,844 KB |
testcase_82 | AC | 13 ms
5,756 KB |
testcase_83 | AC | 197 ms
27,460 KB |
testcase_84 | AC | 189 ms
27,500 KB |
testcase_85 | AC | 102 ms
18,984 KB |
testcase_86 | AC | 153 ms
25,264 KB |
testcase_87 | AC | 172 ms
27,492 KB |
testcase_88 | AC | 23 ms
8,092 KB |
testcase_89 | AC | 197 ms
29,588 KB |
testcase_90 | AC | 115 ms
19,028 KB |
testcase_91 | AC | 88 ms
16,920 KB |
testcase_92 | AC | 46 ms
9,608 KB |
testcase_93 | AC | 146 ms
25,312 KB |
testcase_94 | AC | 131 ms
23,128 KB |
testcase_95 | AC | 130 ms
23,232 KB |
testcase_96 | AC | 177 ms
27,472 KB |
testcase_97 | AC | 75 ms
16,752 KB |
testcase_98 | AC | 181 ms
29,528 KB |
testcase_99 | AC | 105 ms
16,892 KB |
testcase_100 | AC | 200 ms
27,516 KB |
testcase_101 | AC | 39 ms
10,360 KB |
testcase_102 | AC | 21 ms
7,092 KB |
testcase_103 | AC | 44 ms
10,460 KB |
testcase_104 | AC | 62 ms
11,716 KB |
testcase_105 | AC | 148 ms
23,688 KB |
testcase_106 | AC | 82 ms
16,848 KB |
testcase_107 | AC | 205 ms
29,592 KB |
testcase_108 | AC | 194 ms
27,372 KB |
testcase_109 | AC | 154 ms
23,172 KB |
testcase_110 | AC | 137 ms
21,124 KB |
testcase_111 | AC | 141 ms
23,228 KB |
testcase_112 | AC | 59 ms
12,544 KB |
testcase_113 | AC | 123 ms
21,076 KB |
testcase_114 | AC | 80 ms
14,760 KB |
testcase_115 | AC | 26 ms
8,132 KB |
testcase_116 | AC | 96 ms
15,904 KB |
testcase_117 | AC | 58 ms
12,520 KB |
testcase_118 | AC | 181 ms
27,460 KB |
testcase_119 | AC | 103 ms
16,888 KB |
testcase_120 | AC | 172 ms
27,412 KB |
testcase_121 | AC | 51 ms
12,488 KB |
testcase_122 | AC | 92 ms
16,820 KB |
testcase_123 | AC | 1 ms
4,376 KB |
testcase_124 | AC | 260 ms
47,980 KB |
testcase_125 | AC | 262 ms
45,936 KB |
ソースコード
package main import ( "bufio" "fmt" "os" "sort" ) // int main() { // int N; // cin >> N; // NamoriGraph< int > g(N); // g.read(N); // g.build(); // vector< int > ans; // for(auto &e : g.loop_edges) { // ans.emplace_back(e.idx + 1); // } // sort(begin(ans), end(ans)); // cout << ans.size() << "\n"; // cout << ans << "\n"; // } func main() { const INF int = int(1e18) const MOD int = 998244353 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.LoopEdges { res = append(res, e.index+1) } sort.Ints(res) fmt.Fprintln(out, len(res)) for _, v := range res { fmt.Fprint(out, v, " ") } } type Edge = struct{ from, to, cost, index int } type Graph = [][]Edge type NamoriGraph struct { Forest []Graph LoopEdges []Edge g Graph iv [][]int markId, id []int } 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.index) } } 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.index] { continue } edgeUsed[e.index] = true ng.LoopEdges = append(ng.LoopEdges, Edge{i, e.to, e.cost, e.index}) 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.index}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[loop[i]], e.cost, e.index}) ng.buildDfs(e.to, loop[i], tree) } } ng.Forest = append(ng.Forest, tree) } } // 頂点 kについて, サイクルの tree_id, 振り直された木の頂点番号 id を返す。 func (ng *NamoriGraph) GetId(k int) (treeId, id int) { return ng.markId[k], ng.id[k] } // サイクルの tree_id に付属する頂点 kの`もとの頂点番号`を返す。 // 特に GetInvId(tree_id, 0) はサイクルに含まれていたもとの頂点番号を指す。 func (ng *NamoriGraph) GetInvId(treeId, k int) int { return ng.iv[treeId][k] } // markDfs 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) } } } // buildDfs 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.index}) tree[ng.id[e.to]] = append(tree[ng.id[e.to]], Edge{ng.id[e.to], ng.id[idx], e.cost, e.index}) ng.buildDfs(e.to, idx, tree) } } } func max(a, b int) int { if a > b { return a } return b }