結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-11-20 19:13:20 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 242 ms / 3,000 ms |
コード長 | 1,998 bytes |
コンパイル時間 | 11,073 ms |
コンパイル使用メモリ | 237,784 KB |
実行使用メモリ | 27,644 KB |
最終ジャッジ日時 | 2024-10-10 20:12:03 |
合計ジャッジ時間 | 14,543 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
package mainimport ("fmt""bufio""os""strconv""io")var depth []intvar rdepth []intvar graph [][]intconst INF = 114514func dfs(now, par, dep int) int {depth[now] = depmin := INFfor i := 0 ; i < len(graph[now]) ; i++ {to := graph[now][i]if to == par {continue}cn := dfs(to, now, dep+1) + 1if min > cn {min = cn}}if min == INF {min = 0}rdepth[now] = minreturn min}func dfs2(now, par int) {if par >= 0 && rdepth[now] > rdepth[par] + 1 {rdepth[now] = rdepth[par] + 1}for i := 0 ; i < len(graph[now]) ; i++ {to := graph[now][i]if to == par {continue}dfs2(to, now)}}func main() {n := nextInt()edges := make([][]int, n-1)deg := make([]int, n)for i := 0 ; i < n-1 ; i++ {edges[i] = make([]int, 2)a := nextInt()-1b := nextInt()-1deg[a]++deg[b]++edges[i][0] = aedges[i][1] = b}graph = make([][]int, n)for i := 0 ; i < n ; i++ {graph[i] = make([]int, deg[i])}for i := 0 ; i < n-1 ; i++ {a := edges[i][0]b := edges[i][1]deg[a]--deg[b]--graph[a][deg[a]] = bgraph[b][deg[b]] = a}depth = make([]int, n)rdepth = make([]int, n)dfs(0, -1, 0)dfs2(0, -1)for i := 0 ; i < n ; i++ {if depth[i] < rdepth[i] {fmt.Println(depth[i])} else {fmt.Println(rdepth[i])}}}// ====var rdr = bufio.NewReader(os.Stdin)func nextInt() int {i, e := strconv.Atoi(readToken(20))if e != nil {panic(e)}return i}func nextString(limit int) string {return readToken(limit)}func readToken(limit int) string {buf := make([]byte, 0, limit)for {byte, err := rdr.ReadByte()if err != nil {if err == io.EOF {break}}if byte != 10 && byte != 13 && byte != 32 {buf = append(buf, byte)break}}for {byte, err := rdr.ReadByte()if err != nil {if err == io.EOF {break}}if byte == 10 || byte == 13 || byte == 32 {break}buf = append(buf, byte)}return string(buf)}