#866462 (Go) No.2290 UnUnion Find

提出ソース

結果

問題	No.2290 UnUnion Find
ユーザー	ynm3n
提出日時	2023-05-05 22:16:05
言語	Go (1.22.1)
結果	TLE
実行時間	-
コード長	5,401 bytes
コンパイル時間	15,809 ms
コンパイル使用メモリ	217,700 KB
実行使用メモリ	11,264 KB
最終ジャッジ日時	2024-05-02 16:47:21
合計ジャッジ時間	20,577 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 10,624 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	149 ms 5,376 KB
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"math"
	"math/big"
	"os"
	"strconv"
)

// 解答欄
func solve(sc *myScanner, wr *myWriter) {
	n, q := sc.getInt2()
	uf := newUnionFindTree(n)

	for i := 0; i < q; i++ {
		switch typ := sc.getInt(); typ {
		case 1:
			u, v := sc.getInt2()
			u--
			v--
			uf.unite(u, v)
		case 2:
			v := sc.getIntZeroIndexed()
			r := uf.findRoot(v)
			ans := -1
			for u := range uf.roots {
				if r != u {
					ans = u + 1
					break
				}
			}
			wr.println(ans)
		}
	}
}

// UnionFind Tree
type unionFindTree struct {
	// 備忘録
	// 根となる頂点の要素には、特別に以下のような数値が格納されています。
	// 「その根が含まれている木」に含まれる頂点の数にマイナスをかけたもの
	parent []int
	// 連結成分の個数です
	cnt int

	roots map[int]struct{}
}

func newUnionFindTree(n int) *unionFindTree {
	uf := new(unionFindTree)
	uf.parent = make([]int, n)
	for i := range uf.parent {
		uf.parent[i] = -1
	}
	uf.cnt = n
	uf.roots = make(map[int]struct{})
	for i := 0; i < n; i++ {
		uf.roots[i] = struct{}{}
	}
	return uf
}
func (uf *unionFindTree) findRoot(a int) int {
	if uf.parent[a] < 0 {
		return a
	}
	r := uf.findRoot(uf.parent[a])
	if a != r {
		delete(uf.roots, a)
	}
	uf.parent[a] = r
	return r
}
func (uf *unionFindTree) unite(a, b int) bool {
	x, y := uf.findRoot(a), uf.findRoot(b)
	if x == y {
		return false
	}
	if uf.size(x) < uf.size(y) {
		x, y = y, x
	}
	delete(uf.roots, y)
	uf.parent[x] += uf.parent[y]
	uf.parent[y] = x
	uf.cnt--
	return true
}
func (uf *unionFindTree) sameRoot(a, b int) bool {
	return uf.findRoot(a) == uf.findRoot(b)
}
func (uf *unionFindTree) size(a int) int {
	return -uf.parent[uf.findRoot(a)]
}

// 入出力の準備(sc, wr)
func main() {
	sc := &myScanner{bufio.NewScanner(os.Stdin)}
	wr := &myWriter{bufio.NewWriter(os.Stdout)}
	startBufSize := 4096
	maxBufSize := math.MaxInt64
	sc.Buffer(make([]byte, startBufSize), maxBufSize)
	sc.Split(bufio.ScanWords)

	solve(sc, wr)
	wr.Flush()
}

// useful funcs for slice
func makeInts(n, x int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = x
	}
	return res
}
func makeBools(n int, b bool) []bool {
	res := make([]bool, n)
	for i := range res {
		res[i] = b
	}
	return res
}
func countTrue(bs []bool) int {
	res := 0
	for _, b := range bs {
		if b {
			res++
		}
	}
	return res
}

// input
type myScanner struct {
	*bufio.Scanner
}

func (sc *myScanner) getInt() int {
	return sc._getIntOffset(0)
}
func (sc *myScanner) getInt2() (int, int) {
	return sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt3() (int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt4() (int, int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInts(n int) []int {
	return sc._getIntsOffset(n, 0)
}
func (sc *myScanner) getIntZeroIndexed() int {
	return sc._getIntOffset(-1)
}
func (sc *myScanner) getIntsZeroIndexed(n int) []int {
	return sc._getIntsOffset(n, -1)
}
func (sc *myScanner) _getIntOffset(x int) int {
	res, err := strconv.Atoi(sc.getString())
	if err != nil {
		panic(err)
	}
	return res + x
}
func (sc *myScanner) _getIntsOffset(n, x int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = sc._getIntOffset(x)
	}
	return res
}
func (sc *myScanner) getString() string {
	sc.Scan()
	return sc.Text()
}
func (sc *myScanner) getStrings(n int) []string {
	res := make([]string, n)
	for i := range res {
		res[i] = sc.getString()
	}
	return res
}
func (sc *myScanner) getRunes() []rune {
	return []rune(sc.getString())
}
func (sc *myScanner) getFloat() float64 {
	res, err := strconv.ParseFloat(sc.getString(), 64)
	if err != nil {
		panic(err)
	}
	return res
}
func (sc *myScanner) getFloats(n int) []float64 {
	res := make([]float64, n)
	for i := range res {
		res[i] = sc.getFloat()
	}
	return res
}

// output
type myWriter struct {
	*bufio.Writer
}

func (wr *myWriter) println(a ...interface{}) {
	fmt.Fprintln(wr, a...)
}
func (wr *myWriter) printf(format string, a ...interface{}) {
	fmt.Fprintf(wr, format, a...)
}

// simple math funcs for int
func max(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res < a {
			res = a
		}
	}
	return res
}
func min(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res > a {
			res = a
		}
	}
	return res
}
func chMax(a *int, b int) {
	*a = max(*a, b)
}

func chMin(a *int, b int) {
	*a = min(*a, b)
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func pow(a, n int) int {
	res := 1
	b := a
	for n > 0 {
		if n&1 > 0 {
			res *= b
		}
		n >>= 1
		b *= b
	}
	return res
}
func sum(s ...int) int {
	res := 0
	for _, v := range s {
		res += v
	}
	return res
}
func checkPrime(a int) bool {
	if a == 2 {
		return true
	} else if a%2 == 0 {
		return false
	}
	res := true
	for q := 3; q*q <= a; q += 2 {
		if a%q == 0 {
			res = false
			break
		}
	}
	return res
}
func toBInt(a int) *big.Int {
	return big.NewInt(int64(a))
}

/*
	めも
	int(64)の最大値: 9223372036854775807 = (2^63 - 1)
	19桁
	10^18 < 2^60 < 2^63 < 10^19
	10^19 はintだとオーバーフローする

	sliceの長さ: 10^8程度までは許される
	型によるがそれ以上は Out of memory の危険がある

	1~nの和: {n*(n+1)}/2
	(1~nの平均値)*n を式変形したもの
	先に掛け算をすることで必ず2で割り切れる
*/

yukicoder

結果

テストケース

ソースコード