結果

問題 No.416 旅行会社
ユーザー 草苺奶昔草苺奶昔
提出日時 2024-09-08 16:57:58
言語 Go
(1.22.1)
結果
WA  
実行時間 -
コード長 3,772 bytes
コンパイル時間 14,185 ms
コンパイル使用メモリ 226,888 KB
実行使用メモリ 18,432 KB
最終ジャッジ日時 2024-09-08 16:58:21
合計ジャッジ時間 19,960 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 203 ms
11,712 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 205 ms
11,580 KB
testcase_11 AC 197 ms
11,544 KB
testcase_12 AC 201 ms
12,272 KB
testcase_13 AC 190 ms
11,456 KB
testcase_14 AC 426 ms
18,380 KB
testcase_15 AC 408 ms
16,960 KB
testcase_16 AC 408 ms
18,380 KB
testcase_17 AC 424 ms
18,432 KB
testcase_18 AC 406 ms
18,372 KB
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 反向并查集，删边变成加边，然后按照加边的顺序进行操作。
// RemoveEdgeQueriesOffline

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	yuki416()
}

// No.416 旅行会社 (启发式合并+反向并查集删边)
// https://yukicoder.me/problems/no/416
// 对每个点，求第几次删边操作后，无法从该点到达0号点.
// 如果一直可以到达0号点, 输出-1.
func yuki416() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, q int32
	fmt.Fscan(in, &n, &m, &q)
	S := NewRemoveEdgeQueriesOffline(n)
	for i := int32(0); i < m; i++ {
		var u, v int32
		fmt.Fscan(in, &u, &v)
		S.InitEdge(u-1, v-1)
	}
	for i := int32(0); i < q; i++ {
		var u, v int32
		fmt.Fscan(in, &u, &v)
		S.RemoveEdge(u-1, v-1)
	}

	res := make([]int32, n)
	for i := int32(0); i < n; i++ {
		res[i] = -1
	}
	groups := make([][]int32, n)
	for i := int32(0); i < n; i++ {
		groups[i] = []int32{i}
	}
	S.Run(
		func(qi int32, uf *UnionFindArraySimple32, 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] = qi // kth为-1/>=0.
				}
			}

			uf.Union(ra, rb, func(big, small int32) {
				for _, v := range groups[small] {
					groups[big] = append(groups[big], v)
				}
				groups[small] = nil
			})
		},
	)

	for _, v := range res[1:] {
		if v != -1 {
			v++
		}
		fmt.Fprintln(out, v)
	}
}

type RemoveEdgeQueriesOffline struct {
	n            int32
	initialEdges [][2]int32
	removedEdges [][2]int32
	uf           *UnionFindArraySimple32
}

func NewRemoveEdgeQueriesOffline(n int32) *RemoveEdgeQueriesOffline {
	return &RemoveEdgeQueriesOffline{
		n:  n,
		uf: NewUnionFindArraySimple32(n),
	}
}

func (r *RemoveEdgeQueriesOffline) InitEdge(a, b int32) {
	if a > b {
		a, b = b, a
	}
	r.initialEdges = append(r.initialEdges, [2]int32{a, b})
}

func (r *RemoveEdgeQueriesOffline) RemoveEdge(a, b int32) {
	if a > b {
		a, b = b, a
	}
	r.removedEdges = append(r.removedEdges, [2]int32{a, b})
}

// 第kth次操作连接a和b.
//
// k=-1 -> 始终保留的边.
// 第一次删边操作的qi从0开始.
func (r *RemoveEdgeQueriesOffline) Run(f func(qi int32, uf *UnionFindArraySimple32, a, b int32)) {
	removedSet := make(map[[2]int32]struct{}, len(r.removedEdges))
	for _, e := range r.removedEdges {
		removedSet[e] = struct{}{}
	}
	for _, e := range r.initialEdges {
		if _, has := removedSet[e]; !has {
			// keptEdge
			f(-1, r.uf, e[0], e[1])
		}
	}
	for qi := int32(len(r.removedEdges)) - 1; qi >= 0; qi-- {
		f(qi, r.uf, r.removedEdges[qi][0], r.removedEdges[qi][1])
	}
}

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)]
}
0