Submission #1074516

---

Source Code Expand

module Main where

import Control.Applicative
import Control.Monad
import Control.Monad.State
import Data.Array
import Data.Graph

import qualified Data.ByteString.Lazy.Char8 as L

type Tokenizer = State [L.ByteString]

nextInt :: Tokenizer Int
nextInt = state $ \(s:ss) -> case L.readInt s of
                               Just (x, _) -> (x, ss)
                               Nothing -> error $ "Can't parse Int: " ++ (L.unpack s)

maxDepth :: Graph -> Vertex -> Int
maxDepth g u | null ds = 0
             | otherwise = minimum ds + length ds
    where ds = map (maxDepth g) (g ! u)

go :: Tokenizer Int
go = do
  n <- nextInt
  ss <- replicateM (n - 1) nextInt
  let ts = [2 .. n]
      graph = buildG (1, n) (zip ss ts)
  return $ maxDepth graph 1

main :: IO ()
main = do
  contents <- L.words <$> L.getContents
  let depth = evalState go contents
  print depth

Submission Info

Judge Result