#1008224 (Go) No.416 旅行会社

• 問題: No.416 旅行会社
• ユーザー: 草苺奶昔
• 提出日時: 2024-09-08 04:12:48
• 言語: Go (1.23.4)
• 結果: AC
• 実行時間: 426 ms / 4,000 ms
• コード長: 3,097 bytes
• コンパイル時間: 15,971 ms
• コンパイル使用メモリ: 222,612 KB
• 実行使用メモリ: 16,208 KB
• 最終ジャッジ日時: 2024-09-08 04:13:11
• 合計ジャッジ時間: 22,006 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// No.416 旅行会社 (启发式合并+反向并查集删边)
// https://yukicoder.me/problems/no/416
// 给定一个无向图.
// q次断开两条边.
// 对每个点，求第几次删边操作后，无法从该点到达0号点.
// 如果一直可以到达0号点, 输出-1.
package main
import (
    "bufio"
    "fmt"
    "os"
)
func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n, m, q int32
    fmt.Fscan(in, &n, &m, &q)
    edges := make([][2]int32, 0, m)
    for i := int32(0); i < m; i++ {
        var u, v int32
        fmt.Fscan(in, &u, &v)
        edges = append(edges, [2]int32{u - 1, v - 1})
    }
    queries := make([][2]int32, 0, q)
    for i := int32(0); i < q; i++ {
        var u, v int32
        fmt.Fscan(in, &u, &v)
        queries = append(queries, [2]int32{u - 1, v - 1})
    }
    res := make([]int32, n)
    uf := NewUnionFindArraySimple32(n)
    groups := make([][]int32, n)
    for i := int32(0); i < n; i++ {
        groups[i] = []int32{i}
    }
    unionAt := func(time int32, a, b int32) {
        ra, rb := uf.Find(a), uf.Find(b)
        if ra == rb {
            return
        }
        r0 := uf.Find(0)
        // 连接后，原来与0不连通的点，现在连通了，说明删除的这条边是关键的.
        if r0 == ra || r0 == rb {
            other := r0 ^ ra ^ rb
            for _, v := range groups[other] {
                res[v] = time
            }
        }
        uf.Union(ra, rb, func(big, small int32) {
            for _, v := range groups[small] {
                groups[big] = append(groups[big], v)
            }
            groups[small] = nil
        })
    }
    // set(edges) - set(queries)
    keptEdges := func() map[[2]int32]struct{} {
        res, removed := make(map[[2]int32]struct{}), make(map[[2]int32]struct{}, q)
        for _, e := range queries {
            a, b := e[0], e[1]
            if a > b {
                a, b = b, a
            }
            removed[[2]int32{a, b}] = struct{}{}
        }
        for _, e := range edges {
            a, b := e[0], e[1]
            if a > b {
                a, b = b, a
            }
            if _, has := removed[[2]int32{a, b}]; !has {
                res[[2]int32{a, b}] = struct{}{}
            }
        }
        return res
    }()
    for e := range keptEdges {
        unionAt(-1, e[0], e[1])
    }
    for qi := q - 1; qi >= 0; qi-- {
        unionAt(qi+1, queries[qi][0], queries[qi][1])
    }
    for _, v := range res[1:] {
        fmt.Fprintln(out, v)
    }
}
type UnionFindArraySimple32 struct {
    Part int32
    n    int32
    data []int32
}
func NewUnionFindArraySimple32(n int32) *UnionFindArraySimple32 {
    data := make([]int32, n)
    for i := int32(0); i < n; i++ {
        data[i] = -1
    }
    return &UnionFindArraySimple32{Part: n, n: n, data: data}
}
func (u *UnionFindArraySimple32) Union(key1, key2 int32, beforeMerge func(big, small int32)) bool {
    root1, root2 := u.Find(key1), u.Find(key2)
    if root1 == root2 {
        return false
    }
    if u.data[root1] > u.data[root2] {
        root1, root2 = root2, root1
    }
    if beforeMerge != nil {
        beforeMerge(root1, root2)
    }
    u.data[root1] += u.data[root2]
    u.data[root2] = root1
    u.Part--
    return true
}
func (u *UnionFindArraySimple32) Find(key int32) int32 {
    root := key
    for u.data[root] >= 0 {
        root = u.data[root]
    }
    for key != root {
        key, u.data[key] = u.data[key], root
    }
    return root
}
func (u *UnionFindArraySimple32) GetSize(key int32) int32 {
    return -u.data[u.Find(key)]
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX