結果

問題 No.416 旅行会社
ユーザー 草苺奶昔草苺奶昔
提出日時 2024-09-08 17:18:03
言語 Go
(1.22.1)
結果
AC  
実行時間 416 ms / 4,000 ms
コード長 4,060 bytes
コンパイル時間 11,973 ms
コンパイル使用メモリ 233,232 KB
実行使用メモリ 18,368 KB
最終ジャッジ日時 2024-09-08 17:18:23
合計ジャッジ時間 17,482 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 195 ms
12,028 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 23 ms
6,940 KB
testcase_10 AC 208 ms
11,964 KB
testcase_11 AC 201 ms
11,952 KB
testcase_12 AC 208 ms
11,932 KB
testcase_13 AC 191 ms
11,900 KB
testcase_14 AC 405 ms
18,360 KB
testcase_15 AC 410 ms
17,040 KB
testcase_16 AC 416 ms
18,172 KB
testcase_17 AC 411 ms
18,368 KB
testcase_18 AC 413 ms
18,300 KB
testcase_19 AC 268 ms
13,336 KB
testcase_20 AC 259 ms
13,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

package main

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

func main() {
	yuki416()
}

// No.416 旅行会社 (启发式合并+反向并查集删边)
// https://yukicoder.me/problems/no/416
// 对每个点，求第几次删边操作后，无法从该点到达0号点.
// 如果一直可以到达0号点, 输出-1.
// 如果一开始就无法到达0号点, 输出0.
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] = -2
	}
	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 // !qi: -1(始终保留的边) or 0~q-1(第0~q-1次删边操作)
				}
			}

			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 == -2 { // 未连接到0号点
			fmt.Fprintln(out, 0)
		} else if v == -1 { // 一直可以到达0号点
			fmt.Fprintln(out, -1)
		} else { // 第几次删边操作后，无法从该点到达0号点
			fmt.Fprintln(out, v+1)
		}
	}
}

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