結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | 草苺奶昔 |
提出日時 | 2023-06-04 20:08:18 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 3,844 bytes |
コンパイル時間 | 12,072 ms |
コンパイル使用メモリ | 223,736 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-09 04:02:31 |
合計ジャッジ時間 | 14,082 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 10 ms
5,376 KB |
testcase_22 | AC | 9 ms
5,376 KB |
testcase_23 | AC | 10 ms
5,376 KB |
testcase_24 | AC | 9 ms
5,376 KB |
testcase_25 | AC | 8 ms
5,376 KB |
testcase_26 | AC | 5 ms
5,376 KB |
testcase_27 | AC | 4 ms
5,376 KB |
testcase_28 | AC | 7 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 10 ms
5,376 KB |
testcase_31 | AC | 14 ms
5,376 KB |
testcase_32 | AC | 11 ms
5,376 KB |
testcase_33 | AC | 11 ms
5,376 KB |
testcase_34 | AC | 11 ms
5,376 KB |
testcase_35 | AC | 12 ms
5,376 KB |
testcase_36 | AC | 1 ms
5,376 KB |
testcase_37 | AC | 7 ms
5,376 KB |
testcase_38 | AC | 10 ms
5,376 KB |
testcase_39 | AC | 9 ms
5,376 KB |
testcase_40 | AC | 9 ms
5,376 KB |
testcase_41 | AC | 9 ms
5,376 KB |
testcase_42 | AC | 2 ms
5,376 KB |
testcase_43 | AC | 1 ms
5,376 KB |
testcase_44 | AC | 1 ms
5,376 KB |
testcase_45 | AC | 1 ms
5,376 KB |
testcase_46 | AC | 4 ms
5,376 KB |
testcase_47 | AC | 3 ms
5,376 KB |
testcase_48 | AC | 4 ms
5,376 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 2 ms
5,376 KB |
testcase_52 | AC | 3 ms
5,376 KB |
testcase_53 | AC | 2 ms
5,376 KB |
testcase_54 | AC | 2 ms
5,376 KB |
testcase_55 | AC | 4 ms
5,376 KB |
testcase_56 | AC | 1 ms
5,376 KB |
testcase_57 | AC | 2 ms
5,376 KB |
testcase_58 | AC | 1 ms
5,376 KB |
testcase_59 | AC | 2 ms
5,376 KB |
testcase_60 | AC | 1 ms
5,376 KB |
testcase_61 | AC | 2 ms
5,376 KB |
ソースコード
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 } }