#878059 (Go) No.1340 おーじ君をさがせ

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	草苺奶昔
提出日時	2023-06-04 20:08:18
言語	Go (1.22.1)
結果	AC
実行時間	13 ms / 2,000 ms
コード長	3,844 bytes
コンパイル時間	11,410 ms
コンパイル使用メモリ	214,276 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-08-28 08:22:57
合計ジャッジ時間	15,026 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,352 KB
testcase_01	AC	2 ms 4,356 KB
testcase_02	AC	1 ms 4,352 KB
testcase_03	AC	1 ms 4,356 KB
testcase_04	AC	1 ms 4,356 KB
testcase_05	AC	1 ms 4,356 KB
testcase_06	AC	1 ms 4,356 KB
testcase_07	AC	2 ms 4,352 KB
testcase_08	AC	1 ms 4,352 KB
testcase_09	AC	1 ms 4,356 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	2 ms 4,352 KB
testcase_12	AC	2 ms 4,356 KB
testcase_13	AC	2 ms 4,352 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	2 ms 4,356 KB
testcase_16	AC	2 ms 4,360 KB
testcase_17	AC	2 ms 4,352 KB
testcase_18	AC	2 ms 4,356 KB
testcase_19	AC	2 ms 4,356 KB
testcase_20	AC	1 ms 4,356 KB
testcase_21	AC	9 ms 4,356 KB
testcase_22	AC	9 ms 4,356 KB
testcase_23	AC	11 ms 4,356 KB
testcase_24	AC	8 ms 4,352 KB
testcase_25	AC	8 ms 4,352 KB
testcase_26	AC	5 ms 4,356 KB
testcase_27	AC	4 ms 4,352 KB
testcase_28	AC	7 ms 4,352 KB
testcase_29	AC	5 ms 4,352 KB
testcase_30	AC	9 ms 4,376 KB
testcase_31	AC	13 ms 4,352 KB
testcase_32	AC	11 ms 4,356 KB
testcase_33	AC	11 ms 4,360 KB
testcase_34	AC	11 ms 4,356 KB
testcase_35	AC	12 ms 4,352 KB
testcase_36	AC	1 ms 4,356 KB
testcase_37	AC	8 ms 4,360 KB
testcase_38	AC	11 ms 4,356 KB
testcase_39	AC	10 ms 4,356 KB
testcase_40	AC	9 ms 4,356 KB
testcase_41	AC	10 ms 4,352 KB
testcase_42	AC	2 ms 4,352 KB
testcase_43	AC	1 ms 4,356 KB
testcase_44	AC	2 ms 4,356 KB
testcase_45	AC	2 ms 4,356 KB
testcase_46	AC	4 ms 4,356 KB
testcase_47	AC	4 ms 4,352 KB
testcase_48	AC	4 ms 4,360 KB
testcase_49	AC	2 ms 4,356 KB
testcase_50	AC	2 ms 4,356 KB
testcase_51	AC	2 ms 4,352 KB
testcase_52	AC	2 ms 4,356 KB
testcase_53	AC	3 ms 4,352 KB
testcase_54	AC	3 ms 4,356 KB
testcase_55	AC	4 ms 4,356 KB
testcase_56	AC	1 ms 4,356 KB
testcase_57	AC	2 ms 4,376 KB
testcase_58	AC	1 ms 4,352 KB
testcase_59	AC	2 ms 4,352 KB
testcase_60	AC	2 ms 4,352 KB
testcase_61	AC	2 ms 4,352 KB

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

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"strings"
	"time"
)

func main() {
	yuki1340()
}

// https://yukicoder.me/problems/no/1340
func yuki1340() {

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, t int
	fmt.Fscan(in, &n, &m, &t)
	mat := NewBooleanMatrix(n, n)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		mat.Set(a, b, true)
	}
	mat.IPow(t)
	res := 0
	for i := 0; i < n; i++ {
		if mat.Get(0, i) {
			res++
		}
	}
	fmt.Fprintln(out, res)
}

func demo() {
	mat := NewBooleanMatrix(3, 3)
	mat.Set(0, 0, true)
	mat.Set(0, 1, true)
	mat.Set(1, 2, true)
	mat.Set(1, 0, true)
	fmt.Println(mat)
	fmt.Println(Mul(Mul(mat, mat), mat), Pow(mat, 3))
	fmt.Println(Eye(8))

	// 5000*5000的矩阵乘法 => 52ms
	time1 := time.Now()
	eye := Eye(5000)
	Mul(eye, eye)
	time2 := time.Now()
	fmt.Println(time2.Sub(time1))

	// 2000*2000的传递闭包 => 130ms
	time3 := time.Now()
	n := 2000
	newEye := Eye(n)
	TransitiveClosure(newEye)
	time4 := time.Now()
	fmt.Println(time4.Sub(time3))
}

type BooleanMatrix struct {
	ROW, COL int
	bs       []Bitset
}

func NewBooleanMatrix(row, col int) *BooleanMatrix {
	bs := make([]Bitset, row)
	for i := range bs {
		bs[i] = NewBitset(col)
	}
	return &BooleanMatrix{ROW: row, COL: col, bs: bs}
}

func Eye(n int) *BooleanMatrix {
	res := NewBooleanMatrix(n, n)
	for i := 0; i < n; i++ {
		res.bs[i].Set(i)
	}
	return res
}

func Pow(mat *BooleanMatrix, k int) *BooleanMatrix {
	return mat.Copy().IPow(k)
}

func Mul(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	return mat1.Copy().IMul(mat2)
}

func Add(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	return mat1.Copy().IAdd(mat2)
}

// (A + I)^n 是传递闭包.
func TransitiveClosure(mat *BooleanMatrix) *BooleanMatrix {
	n := mat.ROW
	return Pow(Add(mat, Eye(n)), n)
}

func (bm *BooleanMatrix) IPow(k int) *BooleanMatrix {
	res := Eye(bm.ROW)
	for k > 0 {
		if k&1 == 1 {
			res.IMul(bm)
		}
		bm.IMul(bm)
		k >>= 1
	}
	res.bs, bm.bs = bm.bs, res.bs
	return bm
}

func (bm *BooleanMatrix) IMul(mat *BooleanMatrix) *BooleanMatrix {
	row, col := bm.ROW, mat.COL
	res := NewBooleanMatrix(row, col)
	for i := 0; i < row; i++ {
		for j := 0; j < bm.COL; j++ {
			if bm.bs[i].Has(j) {
				res.bs[i].IOr(mat.bs[j])
			}
		}
	}
	bm.bs, res.bs = res.bs, bm.bs
	return bm
}

func (bm *BooleanMatrix) IAdd(mat *BooleanMatrix) *BooleanMatrix {
	for i := 0; i < bm.ROW; i++ {
		bm.bs[i].IOr(mat.bs[i])
	}
	return bm
}

func (bm *BooleanMatrix) Copy() *BooleanMatrix {
	return &BooleanMatrix{ROW: bm.ROW, COL: bm.COL, bs: append(bm.bs[:0:0], bm.bs...)}
}

func (bm *BooleanMatrix) Get(row, col int) bool {
	return bm.bs[row].Has(col)
}

func (bm *BooleanMatrix) Set(row, col int, b bool) {
	if b {
		bm.bs[row].Set(col)
	} else {
		bm.bs[row].Reset(col)
	}
}

// To 2D grid.
func (mat *BooleanMatrix) String() string {
	grid := make([][]int, mat.ROW)
	for i := 0; i < mat.ROW; i++ {
		grid[i] = make([]int, mat.COL)
		for j := 0; j < mat.COL; j++ {
			if mat.Get(i, j) {
				grid[i][j] = 1
			} else {
				grid[i][j] = 0
			}
		}
	}

	sb := strings.Builder{}
	sb.WriteString(fmt.Sprintf("BooleanMatrix(%d,%d)\n", mat.ROW, mat.COL))
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			sb.WriteString(fmt.Sprintf("%d ", grid[i][j]))
		}
		sb.WriteString("\n")
	}

	return sb.String()
}

const _w = bits.UintSize

type Bitset []uint

func NewBitset(n int) Bitset { return make(Bitset, n/_w+1) } // (n+_w-1)/_w

func (b Bitset) Has(p int) bool { return b[p/_w]&(1<<(p%_w)) != 0 }
func (b Bitset) Flip(p int)     { b[p/_w] ^= 1 << (p % _w) }
func (b Bitset) Set(p int)      { b[p/_w] |= 1 << (p % _w) }
func (b Bitset) Reset(p int)    { b[p/_w] &^= 1 << (p % _w) }

// 将 c 的元素合并进 b
func (b Bitset) IOr(c Bitset) {
	for i, v := range c {
		b[i] |= v
	}
}