結果

問題 No.1868 Teleporting Cyanmond
ユーザー 草苺奶昔
提出日時 2024-04-10 22:35:09
言語 Go
(1.23.4)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 9,718 bytes
コンパイル時間 10,459 ms
コンパイル使用メモリ 223,092 KB
実行使用メモリ 55,168 KB
最終ジャッジ日時 2024-10-02 21:02:48
合計ジャッジ時間 14,048 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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

// RangeToRangeGraph ()
// !/
// 线
package main
import (
"bufio"
"fmt"
"os"
)
const INF int = 1e18
func main() {
// CF786B()
yuki1868()
}
// https://www.luogu.com.cn/problem/CF786B
func CF786B() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, q, start int32
fmt.Fscan(in, &n, &q, &start)
start--
G := NewRangeToRangeGraph(n, 0)
newGraph := make([][]neighbor, G.Size())
G.Init(func(from, to int32) { newGraph[from] = append(newGraph[from], neighbor{to, 0}) })
for i := int32(0); i < q; i++ {
var op int32
fmt.Fscan(in, &op)
if op == 1 {
var from, to int32
var weight int
fmt.Fscan(in, &from, &to, &weight)
from--
to--
G.Add(from, to, func(from, to int32) {
newGraph[from] = append(newGraph[from], neighbor{to, weight})
})
} else if op == 2 {
var from, l, r int32
var weight int
fmt.Fscan(in, &from, &l, &r, &weight)
from--
l--
G.AddToRange(from, l, r, func(from, to int32) {
newGraph[from] = append(newGraph[from], neighbor{to, weight})
})
} else if op == 3 {
var to, l, r int32
var weight int
fmt.Fscan(in, &to, &l, &r, &weight)
to--
l--
G.AddFromRange(l, r, to, func(from, to int32) {
newGraph[from] = append(newGraph[from], neighbor{to, weight})
})
}
}
res := DijkstraInt32(int32(len(newGraph)), newGraph, start)
for i := int32(0); i < n; i++ {
fmt.Fprint(out, res[i], " ")
}
}
func yuki1868() {
// https://yukicoder.me/problems/no/1868
// !,ii+1,i+2,...,targets[i]0n-1
// 1itargets[i],1,ii-1,0()
// 2RangeToRangeGraphii+1,i+2,...,targets[i]
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int32
fmt.Fscan(in, &n)
targets := make([]int32, n-1) // !i i+1, i+2, ..., targets[i]
for i := range targets {
fmt.Fscan(in, &targets[i])
targets[i]-- // [0,n-1]
}
R := NewRangeToRangeGraph(n, 0)
adjList := make([][]neighbor, R.Size())
R.Init(func(from, to int32) {
adjList[from] = append(adjList[from], neighbor{to, 0})
})
for i := int32(0); i < n-1; i++ {
R.AddToRange(i, i+1, targets[i]+1, func(from, to int32) {
adjList[from] = append(adjList[from], neighbor{to, 1})
})
}
dist, queue := make([]int, int32(len(adjList))), NewDeque(int32(len(adjList)))
for i := range dist {
dist[i] = INF
}
dist[0] = 0
queue.Append(0)
for queue.Size() > 0 {
cur := queue.PopLeft()
nexts := adjList[cur]
for i := 0; i < len(nexts); i++ {
e := &nexts[i]
next, weight := e.to, e.weight
cand := dist[cur] + weight
if cand < dist[next] {
dist[next] = cand
if weight == 0 {
queue.AppendLeft(next)
} else {
queue.Append(next)
}
}
}
}
fmt.Fprintln(out, dist[n-1])
}
func jump(nums []int) int {
// 45. II
// https://leetcode.cn/problems/jump-game-ii/
n := int32(len(nums))
G := NewRangeToRangeGraph(int32(n), 0)
adjList := make([][]neighbor, G.Size())
G.Init(func(from, to int32) { adjList[from] = append(adjList[from], neighbor{to, 0}) })
for i := int32(0); i < n; i++ {
G.AddToRange(i, i+1, min32(i+1+int32(nums[i]), n), func(from, to int32) {
adjList[from] = append(adjList[from], neighbor{to, 1})
})
}
bfs := func(start int32, adjList [][]neighbor) []int32 {
n := len(adjList)
dist := make([]int32, n)
for i := 0; i < n; i++ {
dist[i] = 1e9
}
dist[start] = 0
queue := []int32{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
nexts := adjList[cur]
for i := 0; i < len(nexts); i++ {
e := &nexts[i]
next, weight := e.to, e.weight
cand := dist[cur] + int32(weight)
if cand < dist[next] {
dist[next] = cand
queue = append(queue, next)
}
}
}
return dist
}
dist := bfs(0, adjList)
return int(dist[n-1])
}
type RangeToRangeGraph struct {
n int32
maxSize int32
allocPtr int32
}
// n rangeToRangeOpCount .
// n*3 + rangeToRangeOpCountn
func NewRangeToRangeGraph(n int32, rangeToRangeOpCount int32) *RangeToRangeGraph {
g := &RangeToRangeGraph{
n: n,
maxSize: n*3 + rangeToRangeOpCount,
allocPtr: n * 3,
}
return g
}
func (g *RangeToRangeGraph) Init(f func(from, to int32)) {
n := g.n
for i := int32(2); i < n+n; i++ {
f(g.toUpperIdx(i>>1), g.toUpperIdx(i))
f(g.toLowerIdx(i), g.toLowerIdx(i>>1))
}
}
// from -> to.
func (g *RangeToRangeGraph) Add(from, to int32, f func(from, to int32)) {
f(from, to)
}
// [fromStart, fromEnd) to .
func (g *RangeToRangeGraph) AddFromRange(fromStart, fromEnd, to int32, f func(from, to int32)) {
l, r := fromStart+g.n, fromEnd+g.n
for l < r {
if l&1 == 1 {
f(g.toLowerIdx(l), to)
l++
}
if r&1 == 1 {
r--
f(g.toLowerIdx(r), to)
}
l >>= 1
r >>= 1
}
}
// from [toStart, toEnd) .
func (g *RangeToRangeGraph) AddToRange(from, toStart, toEnd int32, f func(from, to int32)) {
l, r := toStart+g.n, toEnd+g.n
for l < r {
if l&1 == 1 {
f(from, g.toUpperIdx(l))
l++
}
if r&1 == 1 {
r--
f(from, g.toUpperIdx(r))
}
l >>= 1
r >>= 1
}
}
// [fromStart, fromEnd) [toStart, toEnd) .
func (g *RangeToRangeGraph) AddRangeToRange(fromStart, fromEnd, toStart, toEnd int32, f func(from, to int32)) {
newNode := g.allocPtr
g.allocPtr++
g.AddFromRange(fromStart, fromEnd, newNode, f)
g.AddToRange(newNode, toStart, toEnd, f)
}
// .
func (g *RangeToRangeGraph) Size() int32 { return g.maxSize }
func (g *RangeToRangeGraph) toUpperIdx(i int32) int32 {
if i >= g.n {
return i - g.n
}
return g.n + i
}
func (g *RangeToRangeGraph) toLowerIdx(i int32) int32 {
if i >= g.n {
return i - g.n
}
return g.n + g.n + i
}
type D = int32
type Deque struct{ l, r []D }
func NewDeque(cap int32) *Deque { return &Deque{make([]D, 0, 1+cap/2), make([]D, 0, 1+cap/2)} }
func (q Deque) Empty() bool {
return len(q.l) == 0 && len(q.r) == 0
}
func (q Deque) Size() int {
return len(q.l) + len(q.r)
}
func (q *Deque) AppendLeft(v D) {
q.l = append(q.l, v)
}
func (q *Deque) Append(v D) {
q.r = append(q.r, v)
}
func (q *Deque) PopLeft() (v D) {
if len(q.l) > 0 {
q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
} else {
v, q.r = q.r[0], q.r[1:]
}
return
}
func (q *Deque) Pop() (v D) {
if len(q.r) > 0 {
q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
} else {
v, q.l = q.l[0], q.l[1:]
}
return
}
func (q Deque) Front() D {
if len(q.l) > 0 {
return q.l[len(q.l)-1]
}
return q.r[0]
}
func (q Deque) Back() D {
if len(q.r) > 0 {
return q.r[len(q.r)-1]
}
return q.l[0]
}
// 0 <= i < q.Size()
func (q Deque) At(i int) D {
if i < len(q.l) {
return q.l[len(q.l)-1-i]
}
return q.r[i-len(q.l)]
}
type neighbor struct {
to int32
weight int
}
// -1.
func DijkstraInt32(n int32, graph [][]neighbor, start int32) []int {
pq := NewHeap(func(a, b H) bool { return a.dist < b.dist }, []H{{0, start}})
dist := make([]int, n)
for i := range dist {
dist[i] = INF
}
dist[start] = 0
for pq.Len() > 0 {
cur := pq.Pop()
curDist, curNode := cur.dist, cur.node
if curDist > dist[curNode] {
continue
}
nexts := graph[curNode]
for i := 0; i < len(nexts); i++ {
e := &nexts[i]
next, weight := e.to, e.weight
if tmp := curDist + weight; tmp < dist[next] {
dist[next] = tmp
pq.Push(H{tmp, next})
}
}
}
for i := range dist {
if dist[i] == INF {
dist[i] = -1
}
}
return dist
}
type H = struct {
dist int
node int32
}
func NewHeap(less func(a, b H) bool, nums []H) *Heap {
nums = append(nums[:0:0], nums...)
heap := &Heap{less: less, data: nums}
heap.heapify()
return heap
}
type Heap struct {
data []H
less func(a, b H) bool
}
func (h *Heap) Push(value H) {
h.data = append(h.data, value)
h.pushUp(h.Len() - 1)
}
func (h *Heap) Pop() (value H) {
if h.Len() == 0 {
panic("heap is empty")
}
value = h.data[0]
h.data[0] = h.data[h.Len()-1]
h.data = h.data[:h.Len()-1]
h.pushDown(0)
return
}
func (h *Heap) Top() (value H) {
value = h.data[0]
return
}
func (h *Heap) Len() int { return len(h.data) }
func (h *Heap) heapify() {
n := h.Len()
for i := (n >> 1) - 1; i > -1; i-- {
h.pushDown(i)
}
}
func (h *Heap) pushUp(root int) {
for parent := (root - 1) >> 1; parent >= 0 && h.less(h.data[root], h.data[parent]); parent = (root - 1) >> 1 {
h.data[root], h.data[parent] = h.data[parent], h.data[root]
root = parent
}
}
func (h *Heap) pushDown(root int) {
n := h.Len()
for left := (root<<1 + 1); left < n; left = (root<<1 + 1) {
right := left + 1
minIndex := root
if h.less(h.data[left], h.data[minIndex]) {
minIndex = left
}
if right < n && h.less(h.data[right], h.data[minIndex]) {
minIndex = right
}
if minIndex == root {
return
}
h.data[root], h.data[minIndex] = h.data[minIndex], h.data[root]
root = minIndex
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min32(a, b int32) int32 {
if a < b {
return a
}
return b
}
func max32(a, b int32) int32 {
if a > b {
return a
}
return b
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0