結果

問題 No.2301 Namorientation
ユーザー ynm3nynm3n
提出日時 2023-05-12 23:19:54
言語 Go
(1.22.1)
結果
AC  
実行時間 272 ms / 3,000 ms
コード長 5,273 bytes
コンパイル時間 15,476 ms
コンパイル使用メモリ 247,400 KB
実行使用メモリ 74,240 KB
最終ジャッジ日時 2024-05-06 13:20:40
合計ジャッジ時間 26,782 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 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 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 148 ms
18,048 KB
testcase_13 AC 131 ms
17,024 KB
testcase_14 AC 233 ms
28,288 KB
testcase_15 AC 166 ms
20,992 KB
testcase_16 AC 222 ms
24,576 KB
testcase_17 AC 155 ms
19,044 KB
testcase_18 AC 216 ms
26,368 KB
testcase_19 AC 119 ms
15,588 KB
testcase_20 AC 255 ms
25,344 KB
testcase_21 AC 220 ms
19,556 KB
testcase_22 AC 186 ms
73,344 KB
testcase_23 AC 210 ms
74,240 KB
testcase_24 AC 139 ms
50,688 KB
testcase_25 AC 78 ms
26,052 KB
testcase_26 AC 109 ms
33,896 KB
testcase_27 AC 256 ms
29,256 KB
testcase_28 AC 272 ms
29,132 KB
testcase_29 AC 266 ms
29,000 KB
testcase_30 AC 268 ms
28,752 KB
testcase_31 AC 253 ms
29,132 KB
権限があれば一括ダウンロードができます

ソースコード

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で割り切れる
*/
0