結果

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

ソースコード

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