結果

問題 No.1242 高橋君とすごろく
ユーザー 草苺奶昔草苺奶昔
提出日時 2024-05-01 17:15:34
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 16,820 bytes
コンパイル時間 14,103 ms
コンパイル使用メモリ 233,268 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-21 22:35:44
合計ジャッジ時間 15,099 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 WA -
testcase_11 AC 1 ms
6,816 KB
testcase_12 WA -
testcase_13 AC 2 ms
6,816 KB
testcase_14 WA -
testcase_15 AC 1 ms
6,820 KB
testcase_16 AC 1 ms
6,820 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1 ms
6,816 KB
testcase_21 WA -
testcase_22 AC 2 ms
6,816 KB
testcase_23 AC 2 ms
6,816 KB
testcase_24 AC 2 ms
6,820 KB
testcase_25 AC 1 ms
6,816 KB
testcase_26 WA -
testcase_27 AC 1 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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

// FunctionalGraph-(1,NamoriGraph)
// Directed graphs in which every vertex has exactly one outgoing edge.
// !1()
// =
// 1.
// 2.
// 3.
// 4.
// 5. n3,4,…,n
//
//
//
// 0
// ↓
// 1
// ↙ ↖
// 2 3 ← 4 ← 5
// ↘ ↗
// 6 ← 7
//
// root: 6
// bottom: 3
// to: [1 2 6 1 3 4 3 6]
// directedGraph:
//
// 8 ()
// /
// 6(root)
// / \
// 2 7
// /
// 1
// / \
// 0 3 (bottom)
// \
// 4
// \
// 5
//
// !1.n.
// !2.bottom.
// !3.u()lca(u, bottom).
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
yuki1242()
// abc296_e()
// demo()
}
func demo() {
edges := [][]int{{0, 1, 1}, {1, 2, 1}, {3, 1, 1}, {2, 6, 1}, {6, 3, 9}, {4, 3, 1}, {5, 4, 1}, {7, 6, 1}}
n := int32(8)
F := NewFunctionalGraph(n)
for _, e := range edges {
F.AddDirectedEdge(int32(e[0]), int32(e[1]), e[2])
}
F.Build()
fmt.Println(F.Dist(7, 1, true)) // 11
fmt.Println(F.Dist(7, 1, false)) // 3
fmt.Println(F.Root, F.graph, F.To)
fmt.Println(F.Jump(7, 12)) // 2
fmt.Println(F.JumpAll(100))
for i := int32(0); i < n; i++ {
fmt.Println(F.InCycle(i))
}
for i := int32(0); i < n; i++ {
if F.Root[i] == i {
fmt.Println(F.CollectCycle(i))
}
}
}
// No.1242
// https://yukicoder.me/problems/no/1242
func yuki1242() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, k int32
fmt.Fscan(in, &n, &k)
nums := make([]int32, k)
for i := int32(0); i < k; i++ {
fmt.Fscan(in, &nums[i])
}
G := NewFunctionalGraph(64)
for s := int32(0); s < 64; s++ {
t := (2 * s) & 63
ok := true
if s&1 == 0 && s&32 == 0 {
ok = false
}
if s&2 == 0 && s&16 == 0 {
ok = false
}
if s&4 == 0 && s&8 == 0 {
ok = false
}
if ok {
t |= 1
}
G.AddDirectedEdge(s, t, 1)
}
G.Build()
x := n
s := int32(63)
for i := k - 1; i >= 0; i-- {
y := nums[i]
s = G.Jump(s, x-y)
s &= 62
x = y
}
s = G.Jump(s, x-1)
if s&1 == 1 {
fmt.Fprintln(out, "Yes")
} else {
fmt.Fprintln(out, "No")
}
}
func abc296_e() {
// https://atcoder.jp/contests/abc296/tasks/abc296_e
// ,
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int32
fmt.Fscan(in, &n)
nums := make([]int32, n)
for i := int32(0); i < n; i++ {
fmt.Fscan(in, &nums[i])
}
F := NewFunctionalGraph(n)
for i := int32(0); i < n; i++ {
F.AddDirectedEdge(i, nums[i]-1, 1)
}
F.Build()
res := 0
for i := int32(0); i < n; i++ {
if F.InCycle(i) {
res++
}
}
fmt.Fprintln(out, res)
}
// ,,,-1.
func longestCycle(edges []int) int {
n := int32(len(edges))
F := NewFunctionalGraph(n)
for i := int32(0); i < n; i++ {
if edges[i] != -1 {
F.AddDirectedEdge(i, int32(edges[i]), 1)
} else {
F.AddDirectedEdge(i, i, 1) // !,.
}
}
F.Build()
res := -1
for i := int32(0); i < n; i++ {
if F.Root[i] == i {
cycle := F.CollectCycle(int32(i))
if len(cycle) > 1 {
res = max(res, len(cycle))
}
}
}
return res
}
type neighbor struct {
to int32
weight int
}
type FunctionalGraph struct {
To []int32
Weight []int
Root []int32 //
n, m int32
graph [][]neighbor
tree *Tree
}
func NewFunctionalGraph(n int32) *FunctionalGraph {
to, weight, root := make([]int32, n), make([]int, n), make([]int32, n)
for i := int32(0); i < n; i++ {
to[i] = -1
root[i] = -1
}
return &FunctionalGraph{n: n, To: to, Weight: weight, Root: root}
}
func (f *FunctionalGraph) AddDirectedEdge(from, to int32, weight int) {
if f.To[from] != -1 {
panic("FunctionalGraph: each vertex must have exactly one outgoing edge")
}
f.m++
f.To[from] = to
f.Weight[from] = weight
}
func (f *FunctionalGraph) Build() ([][]neighbor, *Tree) {
if f.n != f.m {
panic("FunctionalGraph: vertex count must be equal to edge count")
}
n := f.n
uf := newUnionFindArraySimple32(n)
for v := int32(0); v < n; v++ {
if !uf.Union(v, f.To[v]) {
f.Root[v] = v
}
}
for v := int32(0); v < n; v++ {
if f.Root[v] == v {
f.Root[uf.Find(v)] = v
}
}
for v := int32(0); v < n; v++ {
f.Root[v] = f.Root[uf.Find(v)]
}
graph := make([][]neighbor, n+1)
for v := int32(0); v < n; v++ {
if f.Root[v] == v {
graph[n] = append(graph[n], neighbor{to: v, weight: f.Weight[v]})
} else {
graph[f.To[v]] = append(graph[f.To[v]], neighbor{to: v, weight: f.Weight[v]})
}
}
f.graph = graph
tree := NewTree(graph)
tree.Build(n)
f.tree = tree
return graph, tree
}
// fromto,-1.
func (f *FunctionalGraph) Dist(from, to int32, weighted bool) int {
if weighted {
if f.tree.IsInSubtree(from, to) {
return f.tree.DepthWeighted[from] - f.tree.DepthWeighted[to]
}
root := f.Root[from]
bottom := f.To[root]
// from -> root -> bottom -> to
if f.tree.IsInSubtree(bottom, to) {
x := f.tree.DepthWeighted[from] - f.tree.DepthWeighted[root]
x += f.Weight[root]
x += f.tree.DepthWeighted[bottom] - f.tree.DepthWeighted[to]
return x
}
return -1
} else {
if f.tree.IsInSubtree(from, to) {
return int(f.tree.Depth[from] - f.tree.Depth[to])
}
root := f.Root[from]
bottom := f.To[root]
// from -> root -> bottom -> to
if f.tree.IsInSubtree(bottom, to) {
x := f.tree.Depth[from] - f.tree.Depth[root]
x++
x += f.tree.Depth[bottom] - f.tree.Depth[to]
return int(x)
}
return -1
}
}
// vstep,,-1.
func (f *FunctionalGraph) Jump(v, step int32) int32 {
d := f.tree.Depth[v]
if step <= d-1 {
return f.tree.Jump(v, f.n, step)
}
v = f.Root[v]
step -= d - 1
bottom := f.To[v]
c := f.tree.Depth[bottom]
step %= c
if step == 0 {
return v
}
return f.tree.Jump(bottom, f.n, step-1)
}
func (f *FunctionalGraph) JumpAll(step int32) []int32 {
n := f.n
res := make([]int32, n)
for v := int32(0); v < n; v++ {
res[v] = -1
}
query := make([][][2]int32, n)
for v := int32(0); v < n; v++ {
d := f.tree.Depth[v]
r := f.Root[v]
if d-1 > step {
query[v] = append(query[v], [2]int32{v, step})
}
if d-1 <= step {
k := step - (d - 1)
bottom := f.To[r]
c := f.tree.Depth[bottom]
k %= c
if k == 0 {
res[v] = r
continue
}
query[bottom] = append(query[bottom], [2]int32{v, k - 1})
}
}
path := []int32{}
var dfs func(int32)
dfs = func(v int32) {
path = append(path, v)
for _, e := range query[v] {
w, k := e[0], e[1]
res[w] = path[int32(len(path))-1-k]
}
for _, e := range f.graph[v] {
dfs(e.to)
}
path = path[:len(path)-1]
}
for _, e := range f.graph[n] {
dfs(e.to)
}
return res
}
func (f *FunctionalGraph) InCycle(v int32) bool {
root := f.Root[v]
bottom := f.To[root]
return f.tree.IsInSubtree(bottom, v)
}
func (f *FunctionalGraph) CollectCycle(r int32) []int32 {
if r != f.Root[r] {
panic("FunctionalGraph: r must be root")
}
cycle := []int32{f.To[r]}
for last := cycle[len(cycle)-1]; last != r; last = cycle[len(cycle)-1] {
cycle = append(cycle, f.To[last])
}
return cycle
}
type Tree struct {
Tree [][]neighbor // (next, weight)
Depth []int32
DepthWeighted []int
Parent []int32
LID, RID []int32 // [in,out)
IdToNode []int32
top, heavySon []int32
timer int32
}
func NewTree(graph [][]neighbor) *Tree {
n := int32(len(graph))
tree := graph
lid := make([]int32, n)
rid := make([]int32, n)
IdToNode := make([]int32, n)
top := make([]int32, n) // /
depth := make([]int32, n) //
depthWeighted := make([]int, n)
parent := make([]int32, n) //
heavySon := make([]int32, n) //
for i := range parent {
parent[i] = -1
}
return &Tree{
Tree: tree,
Depth: depth,
DepthWeighted: depthWeighted,
Parent: parent,
LID: lid,
RID: rid,
IdToNode: IdToNode,
top: top,
heavySon: heavySon,
}
}
// root:0-based
//
// root-10访
func (tree *Tree) Build(root int32) {
if root != -1 {
tree.build(root, -1, 0, 0)
tree.markTop(root, root)
} else {
for i := int32(0); i < int32(len(tree.Tree)); i++ {
if tree.Parent[i] == -1 {
tree.build(i, -1, 0, 0)
tree.markTop(i, i)
}
}
}
}
// root , , 0-indexed.
func (tree *Tree) Id(root int32) (int32, int32) {
return tree.LID[root], tree.RID[root]
}
// u-v , 1 <= eid <= n-1., 0-indexed.
func (tree *Tree) Eid(u, v int32) int32 {
if tree.LID[u] > tree.LID[v] {
return tree.LID[u]
}
return tree.LID[v]
}
func (tree *Tree) LCA(u, v int32) int32 {
for {
if tree.LID[u] > tree.LID[v] {
u, v = v, u
}
if tree.top[u] == tree.top[v] {
return u
}
v = tree.Parent[tree.top[v]]
}
}
func (tree *Tree) RootedLCA(u, v int32, root int32) int32 {
return tree.LCA(u, v) ^ tree.LCA(u, root) ^ tree.LCA(v, root)
}
func (tree *Tree) RootedParent(u int32, root int32) int32 {
return tree.Jump(u, root, 1)
}
func (tree *Tree) Dist(u, v int32, weighted bool) int {
if weighted {
return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]
}
return int(tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)])
}
// k: 0-based
//
// k-1
// kthAncestor(root,0) == root
func (tree *Tree) KthAncestor(root, k int32) int32 {
if k > tree.Depth[root] {
return -1
}
for {
u := tree.top[root]
if tree.LID[root]-k >= tree.LID[u] {
return tree.IdToNode[tree.LID[root]-k]
}
k -= tree.LID[root] - tree.LID[u] + 1
root = tree.Parent[u]
}
}
// from to , step (0-indexed)
//
// ,,-1
func (tree *Tree) Jump(from, to, step int32) int32 {
if step == 1 {
if from == to {
return -1
}
if tree.IsInSubtree(to, from) {
return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
}
return tree.Parent[from]
}
c := tree.LCA(from, to)
dac := tree.Depth[from] - tree.Depth[c]
dbc := tree.Depth[to] - tree.Depth[c]
if step > dac+dbc {
return -1
}
if step <= dac {
return tree.KthAncestor(from, step)
}
return tree.KthAncestor(to, dac+dbc-step)
}
func (tree *Tree) CollectChild(root int32) []int32 {
res := []int32{}
for _, e := range tree.Tree[root] {
next := e.to
if next != tree.Parent[root] {
res = append(res, next)
}
}
return res
}
// 沿`` [,] `` .
//
// !eg:[[2 0] [4 4]] 沿沿.
func (tree *Tree) GetPathDecomposition(u, v int32, vertex bool) [][2]int32 {
up, down := [][2]int32{}, [][2]int32{}
for {
if tree.top[u] == tree.top[v] {
break
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int32{tree.LID[tree.top[v]], tree.LID[v]})
v = tree.Parent[tree.top[v]]
} else {
up = append(up, [2]int32{tree.LID[u], tree.LID[tree.top[u]]})
u = tree.Parent[tree.top[u]]
}
}
edgeInt := int32(1)
if vertex {
edgeInt = 0
}
if tree.LID[u] < tree.LID[v] {
down = append(down, [2]int32{tree.LID[u] + edgeInt, tree.LID[v]})
} else if tree.LID[v]+edgeInt <= tree.LID[u] {
up = append(up, [2]int32{tree.LID[u], tree.LID[v] + edgeInt})
}
for i := 0; i < len(down)/2; i++ {
down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]
}
return append(up, down...)
}
// `[,)` `` .
func (tree *Tree) EnumeratePathDecomposition(u, v int32, vertex bool, f func(start, end int32)) {
for {
if tree.top[u] == tree.top[v] {
break
}
if tree.LID[u] < tree.LID[v] {
a, b := tree.LID[tree.top[v]], tree.LID[v]
if a > b {
a, b = b, a
}
f(a, b+1)
v = tree.Parent[tree.top[v]]
} else {
a, b := tree.LID[u], tree.LID[tree.top[u]]
if a > b {
a, b = b, a
}
f(a, b+1)
u = tree.Parent[tree.top[u]]
}
}
edgeInt := int32(1)
if vertex {
edgeInt = 0
}
if tree.LID[u] < tree.LID[v] {
a, b := tree.LID[u]+edgeInt, tree.LID[v]
if a > b {
a, b = b, a
}
f(a, b+1)
} else if tree.LID[v]+edgeInt <= tree.LID[u] {
a, b := tree.LID[u], tree.LID[v]+edgeInt
if a > b {
a, b = b, a
}
f(a, b+1)
}
}
func (tree *Tree) GetPath(u, v int32) []int32 {
res := []int32{}
composition := tree.GetPathDecomposition(u, v, true)
for _, e := range composition {
a, b := e[0], e[1]
if a <= b {
for i := a; i <= b; i++ {
res = append(res, tree.IdToNode[i])
}
} else {
for i := a; i >= b; i-- {
res = append(res, tree.IdToNode[i])
}
}
}
return res
}
// root,v.
func (tree *Tree) SubSize(v, root int32) int32 {
if root == -1 {
return tree.RID[v] - tree.LID[v]
}
if v == root {
return int32(len(tree.Tree))
}
x := tree.Jump(v, root, 1)
if tree.IsInSubtree(v, x) {
return tree.RID[v] - tree.LID[v]
}
return int32(len(tree.Tree)) - tree.RID[x] + tree.LID[x]
}
// child root (childroot)
func (tree *Tree) IsInSubtree(child, root int32) bool {
return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}
// start top ,heavyPath[-1] .
func (tree *Tree) GetHeavyPath(start int32) []int32 {
heavyPath := []int32{start}
cur := start
for tree.heavySon[cur] != -1 {
cur = tree.heavySon[cur]
heavyPath = append(heavyPath, cur)
}
return heavyPath
}
// v.,-1.
func (tree *Tree) GetHeavyChild(v int32) int32 {
k := tree.LID[v] + 1
if k == int32(len(tree.Tree)) {
return -1
}
w := tree.IdToNode[k]
if tree.Parent[w] == v {
return w
}
return -1
}
func (tree *Tree) ELID(u int32) int32 {
return 2*tree.LID[u] - tree.Depth[u]
}
func (tree *Tree) ERID(u int32) int32 {
return 2*tree.RID[u] - tree.Depth[u] - 1
}
func (tree *Tree) build(cur, pre, dep int32, dist int) int32 {
subSize, heavySize, heavySon := int32(1), int32(0), int32(-1)
for _, e := range tree.Tree[cur] {
next, weight := e.to, e.weight
if next != pre {
nextSize := tree.build(next, cur, dep+1, dist+int(weight))
subSize += nextSize
if nextSize > heavySize {
heavySize, heavySon = nextSize, next
}
}
}
tree.Depth[cur] = dep
tree.DepthWeighted[cur] = dist
tree.heavySon[cur] = heavySon
tree.Parent[cur] = pre
return subSize
}
func (tree *Tree) markTop(cur, top int32) {
tree.top[cur] = top
tree.LID[cur] = tree.timer
tree.IdToNode[tree.timer] = cur
tree.timer++
heavySon := tree.heavySon[cur]
if heavySon != -1 {
tree.markTop(heavySon, top)
for _, e := range tree.Tree[cur] {
next := e.to
if next != heavySon && next != tree.Parent[cur] {
tree.markTop(next, next)
}
}
}
tree.RID[cur] = tree.timer
}
type unionFindArraySimple32 struct {
Part int32
n int32
data []int32
}
func newUnionFindArraySimple32(n int32) *unionFindArraySimple32 {
data := make([]int32, n)
for i := int32(0); i < n; i++ {
data[i] = -1
}
return &unionFindArraySimple32{Part: n, n: n, data: data}
}
func (u *unionFindArraySimple32) Union(key1, key2 int32) bool {
root1, root2 := u.Find(key1), u.Find(key2)
if root1 == root2 {
return false
}
if u.data[root1] > u.data[root2] {
root1, root2 = root2, root1
}
u.data[root1] += u.data[root2]
u.data[root2] = int32(root1)
u.Part--
return true
}
func (u *unionFindArraySimple32) Find(key int32) int32 {
if u.data[key] < 0 {
return key
}
u.data[key] = u.Find(u.data[key])
return u.data[key]
}
func (u *unionFindArraySimple32) GetSize(key int32) int32 {
return -u.data[u.Find(key)]
}
func min(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 max(a, b int) int {
if a > b {
return a
}
return b
}
func max32(a, b int32) int32 {
if a > b {
return a
}
return b
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0