結果

問題 No.1868 Teleporting Cyanmond
ユーザー 草苺奶昔
提出日時 2024-02-09 10:51:17
言語 Go
(1.23.4)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 5,667 bytes
コンパイル時間 10,325 ms
コンパイル使用メモリ 224,448 KB
実行使用メモリ 84,224 KB
最終ジャッジ日時 2024-09-28 12:57:55
合計ジャッジ時間 13,984 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
"bufio"
"fmt"
"os"
)
const INF int = 1e18
func main() {
yuki1868()
}
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 int
fmt.Fscan(in, &n)
targets := make([]int, 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)
for i := 0; i < n-1; i++ {
R.AddToRange(i, i+1, targets[i]+1, 1) //
}
adjList, newN := R.Build()
dist, queue := make([]int, newN), NewDeque(newN)
for i := range dist {
dist[i] = INF
}
dist[0] = 0
queue.Append(0)
for queue.Size() > 0 {
cur := queue.PopLeft()
for _, e := range adjList[cur] {
next, weight := e[0], e[1]
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 := len(nums)
G := NewRangeToRangeGraph(n)
for i := 0; i < n; i++ {
G.AddToRange(i, i+1, min(i+nums[i]+1, n), 1)
}
adjList, _ := G.Build()
bfs := func(start int, adjList [][][2]int) []int {
n := len(adjList)
dist := make([]int, n)
for i := 0; i < n; i++ {
dist[i] = INF
}
dist[start] = 0
queue := []int{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, e := range adjList[cur] {
next, weight := e[0], e[1]
cand := dist[cur] + weight
if cand < dist[next] {
dist[next] = cand
queue = append(queue, next)
}
}
}
return dist
}
dist := bfs(0, adjList)
return dist[n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
type edge struct {
from, to int32
weight int32
}
type RangeToRangeGraph struct {
n int32
nNode int
edges []edge
}
func NewRangeToRangeGraph(n int) *RangeToRangeGraph {
n32 := int32(n)
g := &RangeToRangeGraph{
n: n32,
nNode: n * 3,
}
for i := int32(2); i < n32+n32; i++ {
g.edges = append(g.edges, edge{from: g.toUpperIdx(i / 2), to: g.toUpperIdx(i), weight: 0})
}
for i := int32(2); i < n32+n32; i++ {
g.edges = append(g.edges, edge{from: g.toLowerIdx(i), to: g.toLowerIdx(i / 2), weight: 0})
}
return g
}
// from -> to, weight.
func (g *RangeToRangeGraph) Add(from, to int, weight int) {
g.edges = append(g.edges, edge{from: int32(from), to: int32(to), weight: int32(weight)})
}
// [fromStart, fromEnd) to weight.
func (g *RangeToRangeGraph) AddFromRange(fromStart, fromEnd, to int, weight int) {
l, r := int32(fromStart)+g.n, int32(fromEnd)+g.n
for l < r {
if l&1 == 1 {
g.Add(int(g.toLowerIdx(l)), to, weight)
l++
}
if r&1 == 1 {
r--
g.Add(int(g.toLowerIdx(r)), to, weight)
}
l >>= 1
r >>= 1
}
}
// from [toStart, toEnd) weight.
func (g *RangeToRangeGraph) AddToRange(from, toStart, toEnd int, weight int) {
l, r := int32(toStart)+g.n, int32(toEnd)+g.n
for l < r {
if l&1 == 1 {
g.Add(from, int(g.toUpperIdx(l)), weight)
l++
}
if r&1 == 1 {
r--
g.Add(from, int(g.toUpperIdx(r)), weight)
}
l >>= 1
r >>= 1
}
}
// [fromStart, fromEnd) [toStart, toEnd) weight.
func (g *RangeToRangeGraph) AddRangeToRange(fromStart, fromEnd, toStart, toEnd int, weight int) {
newNode := g.nNode
g.nNode++
g.AddFromRange(fromStart, fromEnd, newNode, weight)
g.AddToRange(newNode, toStart, toEnd, 0)
}
// ``.
func (g *RangeToRangeGraph) Build() (graph [][][2]int, vertex int) {
graph = make([][][2]int, g.nNode)
for i := 0; i < len(g.edges); i++ {
e := &g.edges[i]
u, v, w := e.from, e.to, e.weight
graph[u] = append(graph[u], [2]int{int(v), int(w)})
}
return graph, g.nNode
}
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 = int
type Deque struct{ l, r []D }
func NewDeque(cap int) *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)]
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0