-
Notifications
You must be signed in to change notification settings - Fork 502
/
d.go
46 lines (40 loc) · 959 Bytes
/
d.go
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
package main
import "sort"
// 在线的话可以用最小生成树+倍增
// github.com/EndlessCheng/codeforces-go
type uf struct {
fa []int
}
func newUnionFind(n int) uf {
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
return uf{fa}
}
func (u uf) find(x int) int {
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x])
}
return u.fa[x]
}
func (u uf) merge(from, to int) { u.fa[u.find(from)] = u.find(to) }
func (u uf) same(x, y int) bool { return u.find(x) == u.find(y) }
func distanceLimitedPathsExist(n int, es, qs [][]int) (ans []bool) {
sort.Slice(es, func(i, j int) bool { return es[i][2] < es[j][2] })
ans = make([]bool, len(qs))
u := newUnionFind(n)
for i := range qs {
qs[i] = append(qs[i], i)
}
sort.Slice(qs, func(i, j int) bool { return qs[i][2] < qs[j][2] })
for _, q := range qs {
for len(es) > 0 && es[0][2] < q[2] {
e := es[0]
es = es[1:]
u.merge(e[0], e[1])
}
ans[q[3]] = u.same(q[0], q[1])
}
return
}