東京大学プログラミングコンテスト2013

Submission #137893

Source codeソースコード

{-# LANGUAGE MultiParamTypeClasses,FlexibleContexts,FlexibleInstances,TypeSynonymInstances,BangPatterns,RankNTypes,TupleSections #-}
import Control.Monad
import Control.Monad.ST
import Control.Applicative
import Control.Arrow
import Debug.Trace
import Text.Printf

import Data.List
import Data.Int
import Data.Bits
import Data.Maybe
import Data.Array.Unboxed
import Data.Array.ST
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B

readInt = fromJust . fmap fst . B.readInt
readInts = map readInt . B.words <$> B.getLine
readIntPair = l2p . map readInt . take 2 . B.words <$> B.getLine
readLns :: Read a => IO [a]
readLns = map read . words <$> getLine
cmpFst (a,_) (b,_) = compare a b
cmpSnd (_,a) (_,b) = compare a b
cmpLen a b = length a `compare` length b
swap (a,b) = (b,a)
l2p (a:b:_) = (a,b)
p2l (a,b) = [a,b]
itof :: Int -> Double
itof = fromIntegral
defaultArray :: (IArray a e,Ix i) => e -> (i,i) -> [(i,e)] -> a i e
defaultArray = accumArray $ curry snd
flatten :: [(a,[(b,c)])] -> [((a,b),c)]
flatten = (=<<) $ uncurry $ fmap . first . (,)

main = do
    l <- map (l2p .map readInt. B.words) . B.lines <$> B.getContents
    let ((n1,m1):l1) = l
        (es1,((n2,m2):es2)) = splitAt m1 l1
    let d1 = dist n1 es1
        d2 = dist n2 es2
        rMax1 = maximum $ elems d1
        rMin1 = minimum $ elems d1
        rMax2 = maximum $ elems d2
        rMin2 = minimum $ elems d2
        rMin = maximum [rMax1,rMax2,rMin1 + rMin2 + 1]
        rMax = rMax1 + rMax2 + 1
    printf "%d %d\n" rMin rMax

dist :: Int -> [(Int,Int)] -> UArray Int Int
dist n es = listArray (0,n-1) [ f v | v <- [0..n-1] ]
    where
    g :: Array Int [Int]
    g = accumArray (flip (:)) [] (0,n-1) $ es ++ map swap es
    f v = runST $ do
        r <- newArray (0,n-1) False
        go r [v] [] 0 0
    go :: STUArray s Int Bool -> [Int] ->  [Int] -> Int -> Int -> ST s Int
    go _ [] [] d !acc = return acc
    go vis [] ns d !acc = go vis ns [] (d+1) acc
    go vis (v:l) !ns !d !acc = do
        b <- readArray vis v
        if b then
            go vis l ns d acc
        else do
            writeArray vis v True
            let acc' = max acc d
                ns' = g ! v ++ ns
            go vis l ns' d acc'

Submission

Task問題 C - 直径
User nameユーザ名 autotaker
Created time投稿日時
Language言語 Haskell (GHC 7.4.1)
Status状態 TLE
Score得点 50
Source lengthソースコード長 2331 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Small 50 / 50 10-small_random-00,10-small_random-01,10-small_random-02,10-small_random-03,10-small_random-04,10-small_random-05,10-small_random-06,10-small_random-07,10-small_random-08,10-small_random-09,10-small_random-10,10-small_random-11,10-small_random-12,10-small_random-13,10-small_random-14,10-small_random-15,10-small_random-16,10-small_random-17,10-small_random-18,10-small_random-19,21-small_path-00,21-small_path-01,21-small_path-02,21-small_path-03,21-small_path-04,00-sample-00,00-sample-01,00-sample-02
Large 0 / 50 00-sample-00,00-sample-01,00-sample-02,10-small_random-00,10-small_random-01,10-small_random-02,10-small_random-03,10-small_random-04,10-small_random-05,10-small_random-06,10-small_random-07,10-small_random-08,10-small_random-09,10-small_random-10,10-small_random-11,10-small_random-12,10-small_random-13,10-small_random-14,10-small_random-15,10-small_random-16,10-small_random-17,10-small_random-18,10-small_random-19,20-small_tree-00,20-small_tree-01,20-small_tree-02,20-small_tree-03,20-small_tree-04,21-small_path-00,21-small_path-01,21-small_path-02,21-small_path-03,21-small_path-04,30-large_random-00,30-large_random-01,30-large_random-02,30-large_random-03,30-large_random-04,30-large_random-05,30-large_random-06,30-large_random-07,30-large_random-08,30-large_random-09,40-large_comp-00,40-large_comp-01,40-large_comp-02,40-large_comp-03,40-large_comp-04,41-large_tree-00,41-large_tree-01,41-large_tree-02,41-large_tree-03,41-large_tree-04,42-large_path-00,42-large_path-01,42-large_path-02,42-large_path-03,42-large_path-04

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00-sample-00 AC 77 ms 1308 KB
00-sample-01 AC 28 ms 1308 KB
00-sample-02 AC 25 ms 1312 KB
10-small_random-00 AC 26 ms 1564 KB
10-small_random-01 AC 29 ms 1820 KB
10-small_random-02 AC 28 ms 1384 KB
10-small_random-03 AC 27 ms 1556 KB
10-small_random-04 AC 27 ms 1948 KB
10-small_random-05 AC 30 ms 1820 KB
10-small_random-06 AC 26 ms 1372 KB
10-small_random-07 AC 26 ms 1396 KB
10-small_random-08 AC 27 ms 1308 KB
10-small_random-09 AC 26 ms 1564 KB
10-small_random-10 AC 28 ms 1560 KB
10-small_random-11 AC 28 ms 1436 KB
10-small_random-12 AC 29 ms 1612 KB
10-small_random-13 AC 29 ms 1340 KB
10-small_random-14 AC 30 ms 1816 KB
10-small_random-15 AC 28 ms 1564 KB
10-small_random-16 AC 29 ms 1816 KB
10-small_random-17 AC 29 ms 1944 KB
10-small_random-18 AC 28 ms 1816 KB
10-small_random-19 AC 28 ms 1824 KB
20-small_tree-00 AC 31 ms 1816 KB
20-small_tree-01 AC 27 ms 1304 KB
20-small_tree-02 AC 33 ms 1820 KB
20-small_tree-03 AC 27 ms 1304 KB
20-small_tree-04 AC 275 ms 2336 KB
21-small_path-00 AC 26 ms 1308 KB
21-small_path-01 AC 29 ms 1312 KB
21-small_path-02 AC 27 ms 1312 KB
21-small_path-03 AC 26 ms 1308 KB
21-small_path-04 AC 29 ms 1436 KB
30-large_random-00 AC 405 ms 6296 KB
30-large_random-01 AC 28 ms 1824 KB
30-large_random-02 AC 48 ms 2072 KB
30-large_random-03 AC 26 ms 1352 KB
30-large_random-04 AC 125 ms 2584 KB
30-large_random-05 AC 25 ms 1436 KB
30-large_random-06 AC 51 ms 2080 KB
30-large_random-07 AC 27 ms 1756 KB
30-large_random-08 TLE
30-large_random-09 TLE
40-large_comp-00 AC 29 ms 1312 KB
40-large_comp-01 AC 32 ms 2076 KB
40-large_comp-02 AC 29 ms 1816 KB
40-large_comp-03 AC 49 ms 2716 KB
40-large_comp-04 AC 138 ms 3552 KB
41-large_tree-00 AC 26 ms 1304 KB
41-large_tree-01 AC 28 ms 1820 KB
41-large_tree-02 AC 30 ms 1816 KB
41-large_tree-03 AC 60 ms 1948 KB
41-large_tree-04 AC 276 ms 2328 KB
42-large_path-00 AC 43 ms 1880 KB
42-large_path-01 AC 27 ms 1572 KB
42-large_path-02 AC 25 ms 1692 KB
42-large_path-03 AC 134 ms 2204 KB
42-large_path-04 AC 268 ms 2332 KB