結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-31 00:31:55 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 588 ms / 4,000 ms |
コード長 | 4,635 bytes |
コンパイル時間 | 15,356 ms |
コンパイル使用メモリ | 220,936 KB |
実行使用メモリ | 86,084 KB |
最終ジャッジ日時 | 2023-10-22 07:29:18 |
合計ジャッジ時間 | 29,600 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 2 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 10 ms
4,348 KB |
testcase_09 | AC | 12 ms
4,348 KB |
testcase_10 | AC | 22 ms
7,704 KB |
testcase_11 | AC | 23 ms
5,644 KB |
testcase_12 | AC | 11 ms
4,348 KB |
testcase_13 | AC | 313 ms
26,948 KB |
testcase_14 | AC | 390 ms
33,216 KB |
testcase_15 | AC | 374 ms
29,308 KB |
testcase_16 | AC | 165 ms
18,484 KB |
testcase_17 | AC | 399 ms
33,260 KB |
testcase_18 | AC | 309 ms
29,224 KB |
testcase_19 | AC | 432 ms
41,672 KB |
testcase_20 | AC | 326 ms
29,060 KB |
testcase_21 | AC | 383 ms
35,312 KB |
testcase_22 | AC | 471 ms
51,748 KB |
testcase_23 | AC | 578 ms
48,028 KB |
testcase_24 | AC | 588 ms
45,948 KB |
testcase_25 | AC | 587 ms
48,024 KB |
testcase_26 | AC | 578 ms
45,952 KB |
testcase_27 | AC | 578 ms
48,048 KB |
testcase_28 | AC | 582 ms
48,032 KB |
testcase_29 | AC | 575 ms
45,956 KB |
testcase_30 | AC | 579 ms
45,980 KB |
testcase_31 | AC | 573 ms
48,016 KB |
testcase_32 | AC | 583 ms
48,020 KB |
testcase_33 | AC | 1 ms
4,348 KB |
testcase_34 | AC | 230 ms
18,424 KB |
testcase_35 | AC | 490 ms
83,964 KB |
testcase_36 | AC | 449 ms
25,080 KB |
testcase_37 | AC | 2 ms
4,348 KB |
testcase_38 | AC | 134 ms
5,656 KB |
testcase_39 | AC | 527 ms
86,084 KB |
testcase_40 | AC | 466 ms
41,716 KB |
ソースコード
package main import ( "bufio" "fmt" "os" "strings" ) func criticalConnections(n int, connections [][]int) [][]int { g := make([][]Edge, n) for i := 0; i < len(connections); i++ { u, v := connections[i][0], connections[i][1] g[u] = append(g[u], Edge{from: u, to: v}) g[v] = append(g[v], Edge{from: v, to: u}) } lowLink := NewLowLink(g) lowLink.Build() res := [][]int{} for i := 0; i < len(lowLink.Bridge); i++ { res = append(res, []int{lowLink.Bridge[i].from, lowLink.Bridge[i].to}) } return res } func main() { yuki1983() } func yuki1983() { // https://yukicoder.me/problems/no/1983 // 给定一个无向图 // 对每个查询a,b,问从a到b的路径是否存在且唯一 // !用并查集把所有的桥的端点合并 // 如果起点终点在一个连通分量内,那么答案就是Yes in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m, q int fmt.Fscan(in, &n, &m, &q) graph := make([][]Edge, n) for i := 0; i < m; i++ { var u, v int fmt.Fscan(in, &u, &v) u-- v-- graph[u] = append(graph[u], Edge{u, v}) graph[v] = append(graph[v], Edge{v, u}) } lowlink := NewLowLink(graph) lowlink.Build() uf := NewUnionFindArray(n) for _, e := range lowlink.Bridge { uf.Union(e.from, e.to) } for i := 0; i < q; i++ { var a, b int fmt.Fscan(in, &a, &b) a, b = a-1, b-1 if uf.IsConnected(a, b) { fmt.Fprintln(out, "Yes") } else { fmt.Fprintln(out, "No") } } } type Edge = struct{ from, to int } type LowLink struct { Articulation []int // 関節点 Bridge []Edge // 橋 g [][]Edge ord, low []int used []bool } func NewLowLink(g [][]Edge) *LowLink { return &LowLink{g: g} } func (ll *LowLink) Build() { ll.used = make([]bool, len(ll.g)) ll.ord = make([]int, len(ll.g)) ll.low = make([]int, len(ll.g)) k := 0 for i := 0; i < len(ll.g); i++ { if !ll.used[i] { k = ll.dfs(i, k, -1) } } } func (ll *LowLink) dfs(idx, k, par int) int { ll.used[idx] = true ll.ord[idx] = k k++ ll.low[idx] = ll.ord[idx] isArticulation := false beet := false cnt := 0 for _, e := range ll.g[idx] { if e.to == par { tmp := beet beet = true if !tmp { continue } } if !ll.used[e.to] { cnt++ k = ll.dfs(e.to, k, idx) ll.low[idx] = min(ll.low[idx], ll.low[e.to]) if par >= 0 && ll.low[e.to] >= ll.ord[idx] { isArticulation = true } if ll.ord[idx] < ll.low[e.to] { ll.Bridge = append(ll.Bridge, e) } } else { ll.low[idx] = min(ll.low[idx], ll.ord[e.to]) } } if par == -1 && cnt > 1 { isArticulation = true } if isArticulation { ll.Articulation = append(ll.Articulation, idx) } return k } func min(a, b int) int { if a < b { return a } return b } // // func NewUnionFindArray(n int) *UnionFindArray { parent, rank := make([]int, n), make([]int, n) for i := 0; i < n; i++ { parent[i] = i rank[i] = 1 } return &UnionFindArray{ Part: n, rank: rank, n: n, parent: parent, } } type UnionFindArray struct { // 连通分量的个数 Part int rank []int n int parent []int } func (ufa *UnionFindArray) 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 *UnionFindArray) UnionWithCallback(key1, key2 int, cb func(big, small 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-- cb(root2, root1) return true } func (ufa *UnionFindArray) 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 *UnionFindArray) IsConnected(key1, key2 int) bool { return ufa.Find(key1) == ufa.Find(key2) } func (ufa *UnionFindArray) GetGroups() map[int][]int { groups := make(map[int][]int) for i := 0; i < ufa.n; i++ { root := ufa.Find(i) groups[root] = append(groups[root], i) } return groups } func (ufa *UnionFindArray) Size(key int) int { return ufa.rank[ufa.Find(key)] } func (ufa *UnionFindArray) String() string { sb := []string{"UnionFindArray:"} for root, member := range ufa.GetGroups() { cur := fmt.Sprintf("%d: %v", root, member) sb = append(sb, cur) } sb = append(sb, fmt.Sprintf("Part: %d", ufa.Part)) return strings.Join(sb, "\n") }