結果

問題 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
	}
}
0