結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2023-06-04 20:08:18 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 3,844 bytes |
コンパイル時間 | 11,452 ms |
コンパイル使用メモリ | 219,708 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-29 03:46:24 |
合計ジャッジ時間 | 12,793 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
package mainimport ("bufio""fmt""math/bits""os""strings""time")func main() {yuki1340()}// https://yukicoder.me/problems/no/1340func yuki1340() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n, m, t intfmt.Fscan(in, &n, &m, &t)mat := NewBooleanMatrix(n, n)for i := 0; i < m; i++ {var a, b intfmt.Fscan(in, &a, &b)mat.Set(a, b, true)}mat.IPow(t)res := 0for 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的矩阵乘法 => 52mstime1 := time.Now()eye := Eye(5000)Mul(eye, eye)time2 := time.Now()fmt.Println(time2.Sub(time1))// 2000*2000的传递闭包 => 130mstime3 := time.Now()n := 2000newEye := Eye(n)TransitiveClosure(newEye)time4 := time.Now()fmt.Println(time4.Sub(time3))}type BooleanMatrix struct {ROW, COL intbs []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.ROWreturn 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.bsreturn bm}func (bm *BooleanMatrix) IMul(mat *BooleanMatrix) *BooleanMatrix {row, col := bm.ROW, mat.COLres := 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.bsreturn 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.UintSizetype Bitset []uintfunc NewBitset(n int) Bitset { return make(Bitset, n/_w+1) } // (n+_w-1)/_wfunc (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 的元素合并进 bfunc (b Bitset) IOr(c Bitset) {for i, v := range c {b[i] |= v}}