結果

問題 No.2301 Namorientation
ユーザー ynm3n
提出日時 2023-05-12 23:19:54
言語 Go
(1.23.4)
結果
AC  
実行時間 261 ms / 3,000 ms
コード長 5,273 bytes
コンパイル時間 17,410 ms
コンパイル使用メモリ 221,244 KB
実行使用メモリ 73,856 KB
最終ジャッジ日時 2024-11-28 20:08:47
合計ジャッジ時間 29,242 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "math"
    "math/big"
    "os"
    "strconv"
)
// 解答欄
func solve(sc *myScanner, wr *myWriter) {
    type edge struct {
        idx, to     int
        left, right int
    }
    n := sc.getInt()
    graph := make([][]edge, n)
    for i := 0; i < n; i++ {
        a, b := sc.getInt2()
        a--
        b--
        graph[a] = append(graph[a], edge{i, b, a, b})
        graph[b] = append(graph[b], edge{i, a, a, b})
    }
    loop := func() []bool {
        loop := make([]bool, n)
        visited := make([]bool, n)
        calculating := make([]bool, n)
        var dfs func(prev, now int) int
        dfs = func(prev, now int) int {
            if visited[now] {
                if calculating[now] {
                    return now
                }
                return -1
            }
            visited[now] = true
            calculating[now] = true
            res := -1
            for _, ne := range graph[now] {
                next := ne.to
                if next == prev {
                    continue
                }
                if x := dfs(now, next); x >= 0 {
                    loop[now] = true
                    if now != x {
                        res = x
                    }
                    break
                }
            }
            calculating[now] = false
            return res
        }
        dfs(-1, 0)
        return loop
    }()
    // false: 左矢印
    // true: 右矢印
    ans := make([]bool, n)
    decided := make([]bool, n)
    for i, b := range loop {
        if !b {
            continue
        }
        start := i
        var dfs func(prev, now int)
        dfs = func(prev, now int) {
            if now == start && prev != -1 {
                return
            }
            for _, e := range graph[now] {
                if e.to == prev {
                    continue
                }
                if e.left != now && !decided[e.idx] {
                    ans[e.idx] = true
                }
                decided[e.idx] = true
                dfs(now, e.to)
            }
        }
        dfs(-1, start)
        break
    }
    for _, b := range ans {
        a := "<-"
        if b {
            a = "->"
        }
        wr.println(a)
    }
}
// 入出力の準備(sc, wr)
func main() {
    sc := &myScanner{bufio.NewScanner(os.Stdin)}
    wr := &myWriter{bufio.NewWriter(os.Stdout)}
    startBufSize := 4096
    maxBufSize := math.MaxInt64
    sc.Buffer(make([]byte, startBufSize), maxBufSize)
    sc.Split(bufio.ScanWords)
    solve(sc, wr)
    wr.Flush()
}
// useful funcs for slice
func makeInts(n, x int) []int {
    res := make([]int, n)
    for i := range res {
        res[i] = x
    }
    return res
}
func makeBools(n int, b bool) []bool {
    res := make([]bool, n)
    for i := range res {
        res[i] = b
    }
    return res
}
func countTrue(bs []bool) int {
    res := 0
    for _, b := range bs {
        if b {
            res++
        }
    }
    return res
}
// input
type myScanner struct {
    *bufio.Scanner
}
func (sc *myScanner) getInt() int {
    return sc._getIntOffset(0)
}
func (sc *myScanner) getInt2() (int, int) {
    return sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt3() (int, int, int) {
    return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt4() (int, int, int, int) {
    return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInts(n int) []int {
    return sc._getIntsOffset(n, 0)
}
func (sc *myScanner) getIntZeroIndexed() int {
    return sc._getIntOffset(-1)
}
func (sc *myScanner) getIntsZeroIndexed(n int) []int {
    return sc._getIntsOffset(n, -1)
}
func (sc *myScanner) _getIntOffset(x int) int {
    res, err := strconv.Atoi(sc.getString())
    if err != nil {
        panic(err)
    }
    return res + x
}
func (sc *myScanner) _getIntsOffset(n, x int) []int {
    res := make([]int, n)
    for i := range res {
        res[i] = sc._getIntOffset(x)
    }
    return res
}
func (sc *myScanner) getString() string {
    sc.Scan()
    return sc.Text()
}
func (sc *myScanner) getStrings(n int) []string {
    res := make([]string, n)
    for i := range res {
        res[i] = sc.getString()
    }
    return res
}
func (sc *myScanner) getRunes() []rune {
    return []rune(sc.getString())
}
func (sc *myScanner) getFloat() float64 {
    res, err := strconv.ParseFloat(sc.getString(), 64)
    if err != nil {
        panic(err)
    }
    return res
}
func (sc *myScanner) getFloats(n int) []float64 {
    res := make([]float64, n)
    for i := range res {
        res[i] = sc.getFloat()
    }
    return res
}
// output
type myWriter struct {
    *bufio.Writer
}
func (wr *myWriter) println(a ...interface{}) {
    fmt.Fprintln(wr, a...)
}
func (wr *myWriter) printf(format string, a ...interface{}) {
    fmt.Fprintf(wr, format, a...)
}
// simple math funcs for int
func max(as ...int) int {
    res := as[0]
    for _, a := range as {
        if res < a {
            res = a
        }
    }
    return res
}
func min(as ...int) int {
    res := as[0]
    for _, a := range as {
        if res > a {
            res = a
        }
    }
    return res
}
func chMax(a *int, b int) {
    *a = max(*a, b)
}
func chMin(a *int, b int) {
    *a = min(*a, b)
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
func pow(a, n int) int {
    res := 1
    b := a
    for n > 0 {
        if n&1 > 0 {
            res *= b
        }
        n >>= 1
        b *= b
    }
    return res
}
func sum(s ...int) int {
    res := 0
    for _, v := range s {
        res += v
    }
    return res
}
func checkPrime(a int) bool {
    if a == 2 {
        return true
    } else if a%2 == 0 {
        return false
    }
    res := true
    for q := 3; q*q <= a; q += 2 {
        if a%q == 0 {
            res = false
            break
        }
    }
    return res
}
func toBInt(a int) *big.Int {
    return big.NewInt(int64(a))
}
/*
    めも
    int(64)の最大値: 9223372036854775807 = (2^63 - 1)
    19桁
    10^18 < 2^60 < 2^63 < 10^19
    10^19 はintだとオーバーフローする
    sliceの長さ: 10^8程度までは許される
    型によるがそれ以上は Out of memory の危険がある
    1~nの和: {n*(n+1)}/2
    (1~nの平均値)*n を式変形したもの
    先に掛け算をすることで必ず2で割り切れる
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0