結果
問題 | No.1639 最小通信路 |
ユーザー |
|
提出日時 | 2022-07-09 17:37:07 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,272 bytes |
コンパイル時間 | 11,922 ms |
コンパイル使用メモリ | 222,856 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-31 06:01:36 |
合計ジャッジ時間 | 14,183 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
package mainimport ("bufio""fmt""os""strconv")var sc = bufio.NewScanner(os.Stdin)var out = bufio.NewWriter(os.Stdout)func solve(n int, a, b []int, c []string) string {uf := NewUnionFind(n)m := n * (n - 1) / 2for i := 0; i < m; i++ {uf.Unite(a[i], b[i])if uf.Size(1) == n {return c[i]}}return c[m-1]}func main() {buf := make([]byte, 1024*1024)sc.Buffer(buf, bufio.MaxScanTokenSize)sc.Split(bufio.ScanWords)n := nextInt()var a, b []intvar c []stringfor i := 0; i < n*(n-1)/2; i++ {a = append(a, nextInt())b = append(b, nextInt())c = append(c, nextString())}ans := solve(n, a, b, c)PrintString(ans)}func nextInt() int {sc.Scan()i, _ := strconv.Atoi(sc.Text())return i}func nextString() string {sc.Scan()return sc.Text()}func PrintString(x string) {defer out.Flush()fmt.Fprintln(out, x)}type UnionFind struct {par []int // parent numbersrank []int // height of treesize []int}func NewUnionFind(n int) *UnionFind {if n <= 0 {return nil}u := new(UnionFind)// for accessing index without minus 1u.par = make([]int, n+1)u.rank = make([]int, n+1)u.size = make([]int, n+1)for i := 0; i <= n; i++ {u.par[i] = iu.rank[i] = 0u.size[i] = 1}return u}func (this *UnionFind) Find(x int) int {if this.par[x] == x {return x} else {// compress path// ex. Find(4)// 1 - 2 - 3 - 4// 1 - 2// L-3// L 4this.par[x] = this.Find(this.par[x])return this.par[x]}}func (this *UnionFind) Size(x int) int {return this.size[this.Find(x)]}func (this *UnionFind) ExistSameUnion(x, y int) bool {return this.Find(x) == this.Find(y)}func (this *UnionFind) Unite(x, y int) {x = this.Find(x)y = this.Find(y)if x == y {return}// rankif this.rank[x] < this.rank[y] {//yがrootの木にxがrootの木を結合するthis.par[x] = ythis.size[y] += this.size[x]} else {// this.rank[x] >= this.rank[y]//xがrootの木にyがrootの木を結合するthis.par[y] = xthis.size[x] += this.size[y]if this.rank[x] == this.rank[y] {this.rank[x]++}}}func PrintUnionFind(u *UnionFind) {// for debuging. not optimize.fmt.Println(u.par)fmt.Println(u.rank)fmt.Println(u.size)}