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

Submission #140760

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.Base
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 $ d1
        rMin1 = minimum $ d1
        rMax2 = maximum $ d2
        rMin2 = minimum $ d2
        rMin = maximum [rMax1,rMax2,rMin1 + rMin2 + 1]
        rMax = rMax1 + rMax2 + 1
    printf "%d %d\n" rMin rMax

inf :: Int
inf = 10^9

dist :: Int -> [(Int,Int)] -> [Int]
dist n es = do
    v <- [0..n-1]
    return $ runST $ do
        r <- newArray (0,n-1) True :: ST s (STUArray s Int Bool)
        unsafeWrite r v False
        go r 1 [v] []
    where
    g :: Array Int [Int]
    g = accumArray (flip (:)) [] (0,n-1) $ es ++ map swap es
    go r d [] [] = return (d-1)
    go r d [] !ns = go r (d+1) ns []
    go r d (v:vs) !ns = gosub (unsafeAt g v) ns
        where
        gosub [] !ns = go r d vs ns
        gosub (u:us) !ns = do
            b <- unsafeRead r u
            if b then do
                unsafeWrite r u False
                gosub us (u:ns)
            else
                gosub us ns

Submission

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

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 50 / 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 88 ms 1192 KB
00-sample-01 AC 26 ms 1240 KB
00-sample-02 AC 25 ms 1236 KB
10-small_random-00 AC 25 ms 1364 KB
10-small_random-01 AC 27 ms 1444 KB
10-small_random-02 AC 25 ms 1240 KB
10-small_random-03 AC 27 ms 1316 KB
10-small_random-04 AC 26 ms 1364 KB
10-small_random-05 AC 26 ms 1496 KB
10-small_random-06 AC 25 ms 1240 KB
10-small_random-07 AC 26 ms 1388 KB
10-small_random-08 AC 28 ms 1304 KB
10-small_random-09 AC 26 ms 1364 KB
10-small_random-10 AC 26 ms 1380 KB
10-small_random-11 AC 26 ms 1360 KB
10-small_random-12 AC 24 ms 1364 KB
10-small_random-13 AC 25 ms 1248 KB
10-small_random-14 AC 27 ms 1488 KB
10-small_random-15 AC 26 ms 1428 KB
10-small_random-16 AC 26 ms 1496 KB
10-small_random-17 AC 26 ms 1492 KB
10-small_random-18 AC 26 ms 1552 KB
10-small_random-19 AC 26 ms 1492 KB
20-small_tree-00 AC 29 ms 1748 KB
20-small_tree-01 AC 25 ms 1192 KB
20-small_tree-02 AC 29 ms 1748 KB
20-small_tree-03 AC 25 ms 1184 KB
20-small_tree-04 AC 146 ms 2260 KB
21-small_path-00 AC 26 ms 1236 KB
21-small_path-01 AC 26 ms 1296 KB
21-small_path-02 AC 26 ms 1232 KB
21-small_path-03 AC 27 ms 1228 KB
21-small_path-04 AC 26 ms 1280 KB
30-large_random-00 AC 131 ms 5204 KB
30-large_random-01 AC 26 ms 1368 KB
30-large_random-02 AC 33 ms 2004 KB
30-large_random-03 AC 26 ms 1300 KB
30-large_random-04 AC 70 ms 2564 KB
30-large_random-05 AC 25 ms 1236 KB
30-large_random-06 AC 38 ms 1876 KB
30-large_random-07 AC 27 ms 1680 KB
30-large_random-08 AC 1133 ms 6484 KB
30-large_random-09 AC 1117 ms 6488 KB
40-large_comp-00 AC 26 ms 1236 KB
40-large_comp-01 AC 30 ms 2008 KB
40-large_comp-02 AC 26 ms 1748 KB
40-large_comp-03 AC 37 ms 2648 KB
40-large_comp-04 AC 70 ms 3408 KB
41-large_tree-00 AC 26 ms 1192 KB
41-large_tree-01 AC 27 ms 1748 KB
41-large_tree-02 AC 28 ms 1752 KB
41-large_tree-03 AC 42 ms 1744 KB
41-large_tree-04 AC 146 ms 2272 KB
42-large_path-00 AC 32 ms 1752 KB
42-large_path-01 AC 28 ms 1320 KB
42-large_path-02 AC 27 ms 1580 KB
42-large_path-03 AC 80 ms 2004 KB
42-large_path-04 AC 143 ms 2392 KB