結果

問題 No.1390 Get together
コンテスト
ユーザー ID 21712
提出日時 2026-05-25 19:55:16
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 1,131 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,191 ms
コンパイル使用メモリ 279,656 KB
実行使用メモリ 18,196 KB
最終ジャッジ日時 2026-05-25 19:55:34
合計ジャッジ時間 16,303 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m int
	Fscan(rd,&n,&m)
	table := make([][]int, n+1)
	for i := 0; i < n; i++ {
		var b, c int
		Fscan(rd,&b,&c)
		table[c] = append(table[c], b)
	}
	ans := 0
	for _, bs := range table {
		for i := 0; i < len(bs)-1; i++ {
			if isSame(bs[i],bs[i+1]) {
				continue
			}
			union(bs[i],bs[i+1])
			ans++
		}
	}
	Println(ans)
}

var group [2e5+10]int
var place [2e5+10]int
var groupId int = 0

func getGroup(a int) int {
	g := place[a]
	for g != group[g] {
		g = group[g]
	}
	place[a] = g
	return g
}

func isSame(a, b int) bool {
	ga := getGroup(a)
	gb := getGroup(b)
	return ga != 0 && ga == gb
}

func union(a, b int) {
	ga := getGroup(a)
	gb := getGroup(b)
	switch {
		case ga == 0 && gb == 0:
			groupId++
			place[a] = groupId
			place[b] = groupId
			group[groupId] = groupId
		case ga == 0:
			place[a] = gb
		case gb == 0:
			place[b] = ga
		default:
			ga,gb = min(ga,gb),max(ga,gb)
			group[gb] = ga
	}
}


/*
考察

UnionFind使う問題ぽく感じる
実装うろ覚えなのでうまくいくか・・・？

*/
0