結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0