結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー | 草苺奶昔 |
提出日時 | 2023-12-24 02:01:50 |
言語 | Go (1.22.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,555 bytes |
コンパイル時間 | 12,312 ms |
コンパイル使用メモリ | 224,752 KB |
実行使用メモリ | 37,220 KB |
最終ジャッジ日時 | 2024-09-27 13:33:17 |
合計ジャッジ時間 | 24,280 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | RE | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | WA | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | WA | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 233 ms
13,672 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | RE | - |
testcase_38 | WA | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
ソースコード
package mainimport ("bufio""fmt""os""strings")func main() {Yuki1983()// yosupo()}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 intfmt.Fscan(in, &n, &m, &q)graph := make([][]Neighbor, n)edges := make([][2]int, 0, m)for i := 0; i < m; i++ {var u, v intfmt.Fscan(in, &u, &v)u, v = u-1, v-1edges = append(edges, [2]int{u, v})graph[u] = append(graph[u], Neighbor{u, v})graph[v] = append(graph[v], Neighbor{v, u})}_, belong := TwoEdgeComponent(n, m, graph)uf := NewUnionFindArray(n)for _, e := range edges {u, v := e[0], e[1]if belong[u] != belong[v] { // (u,v)是桥uf.Union(u, v)}}for i := 0; i < q; i++ {var a, b intfmt.Fscan(in, &a, &b)a, b = a-1, b-1if uf.IsConnected(a, b) {fmt.Fprintln(out, "Yes")} else {fmt.Fprintln(out, "No")}}}// https://judge.yosupo.jp/problem/two_edge_connected_componentsfunc yosupo() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n, m intfmt.Fscan(in, &n, &m)g := make([][]Neighbor, n)for i := 0; i < m; i++ {var u, v intfmt.Fscan(in, &u, &v)g[u] = append(g[u], Neighbor{v, i})g[v] = append(g[v], Neighbor{u, i})}count, belong := TwoEdgeComponent(n, m, g)group := make([][]int, count)for i := 0; i < n; i++ {group[belong[i]] = append(group[belong[i]], i)}fmt.Fprintln(out, count)for _, p := range group {fmt.Fprint(out, len(p))for _, v := range p {fmt.Fprint(out, " ", v)}fmt.Fprintln(out)}}type Neighbor = struct{ to, id int }// 求无向图的边双连通分量.// 返回值为 (边双连通分量数, 每个点所属的边双连通分量编号).// !如果某条边(u,v)满足 `belong[u]!=belong[v]`,则称该边为桥.func TwoEdgeComponent(n, m int, graph [][]Neighbor) (count int, belong []int) {path := make([]int, 0, n)parent := make([]int, n)for i := range parent {parent[i] = -2}dp := make([]int, n)belong = make([]int, n)used := make([]bool, m)var dfs func(int)dfs = func(v int) {path = append(path, v)for _, e := range graph[v] {if used[e.id] {continue}used[e.id] = trueif parent[e.to] == -2 {parent[e.to] = vdfs(e.to)} else {dp[v]++dp[e.to]--}}}for v := 0; v < n; v++ {if parent[v] == -2 {parent[v] = -1dfs(v)}}for i := n - 1; i >= 0; i-- {v := path[i]if parent[v] != -1 {dp[parent[v]] += dp[v]}}for _, v := range path {if dp[v] == 0 {belong[v] = countcount++} else {belong[v] = belong[parent[v]]}}return}// 边双缩点成树.// func ToDag(n, m int, graph [][]Neighbor) (dag [][]int) {}func NewUnionFindArray(n int) *_UnionFindArray {parent, rank := make([]int, n), make([]int, n)for i := 0; i < n; i++ {parent[i] = irank[i] = 1}return &_UnionFindArray{Part: n,rank: rank,n: n,parent: parent,}}type _UnionFindArray struct {// 连通分量的个数Part intrank []intn intparent []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] = root2ufa.rank[root2] += ufa.rank[root1]ufa.Part--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")}