Submission #6433022


Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	a := getNextInt(scanner) - 1
	b := getNextInt(scanner) - 1

	m := getNextInt(scanner)

	var dp [101][100]int
	var ll [100][]int

	dp[0][a] = 1

	for i := 0; i < n; i++ {
		ll[i] = []int{}
	}

	for i := 0; i < m; i++ {
		x := getNextInt(scanner) - 1
		y := getNextInt(scanner) - 1
		ll[x] = append(ll[x], y)
		ll[y] = append(ll[y], x)
	}

	for i := 0; i < n; i++ {
		for ii := 0; ii < n; ii++ {
			if dp[i][ii] == 0 {
				continue
			}
			for _, x := range ll[ii] {
				dp[i+1][x] += dp[i][ii]
				dp[i+1][x] %= int(1e9 + 7)
			}
		}
	}

	ans := 0
	for i := 0; i < n; i++ {
		if dp[i][b] > 0 {
			ans = dp[i][b]
			break
		}
	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User ccppjsrb
Language Go (1.6)
Score 100
Code Size 1491 Byte
Status AC
Exec Time 2 ms
Memory 768 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 768 KB
subtask0_sample_02.txt AC 1 ms 768 KB
subtask1_01.txt AC 1 ms 768 KB
subtask1_02.txt AC 1 ms 768 KB
subtask1_03.txt AC 1 ms 768 KB
subtask1_04.txt AC 1 ms 768 KB
subtask1_05.txt AC 1 ms 768 KB
subtask1_06.txt AC 1 ms 768 KB
subtask1_07.txt AC 1 ms 768 KB
subtask1_08.txt AC 1 ms 768 KB
subtask1_09.txt AC 1 ms 768 KB
subtask1_10.txt AC 1 ms 768 KB
subtask1_11.txt AC 1 ms 768 KB
subtask1_12.txt AC 1 ms 768 KB
subtask1_13.txt AC 1 ms 768 KB
subtask1_14.txt AC 1 ms 768 KB
subtask1_15.txt AC 1 ms 768 KB
subtask1_16.txt AC 2 ms 768 KB
subtask1_17.txt AC 1 ms 768 KB
subtask1_18.txt AC 2 ms 768 KB
subtask1_19.txt AC 2 ms 768 KB
subtask1_20.txt AC 2 ms 768 KB
subtask1_21.txt AC 2 ms 768 KB
subtask1_22.txt AC 1 ms 768 KB
subtask1_23.txt AC 1 ms 768 KB
subtask1_24.txt AC 1 ms 768 KB
subtask1_25.txt AC 1 ms 768 KB
subtask1_26.txt AC 1 ms 768 KB
subtask1_27.txt AC 1 ms 768 KB
subtask1_28.txt AC 1 ms 768 KB
subtask1_29.txt AC 1 ms 768 KB
subtask1_30.txt AC 1 ms 768 KB