結果
問題 | No.583 鉄道同好会 |
ユーザー | pekempey |
提出日時 | 2017-10-28 15:36:15 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,462 bytes |
コンパイル時間 | 456 ms |
コンパイル使用メモリ | 150,016 KB |
最終ジャッジ日時 | 2024-05-01 20:56:41 |
合計ジャッジ時間 | 898 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:7:1: error: [GHC-87110] Could not load module ‘Data.Set’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 7 | import Data.Set (Set, fromList, toList, insert, member, empty) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:8:1: error: [GHC-87110] Could not load module ‘Data.Set’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 8 | import qualified Data.Set as S | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
import Control.Applicative import Control.Monad import Control.Monad.ST import Debug.Trace import Data.List hiding (insert) import Data.Array import Data.Set (Set, fromList, toList, insert, member, empty) import qualified Data.Set as S import Data.Array.ST import qualified Data.ByteString.Char8 as B main :: IO () main = solve <$> (map readInt . B.words <$> B.getLine) <*> (map (map readInt . B.words) . B.lines <$> B.getContents) >>= putStrLn . yesno readInt :: B.ByteString -> Int readInt = maybe undefined fst . B.readInt yesno :: Bool -> String yesno True = "YES" yesno False = "NO" solve :: [Int] -> [[Int]] -> Bool solve [n, m] [] = True solve [n, m] es = let g = toArray n es deg = map length . elems $ g in if (all even) deg || (length . filter odd) deg == 2 then let reachable = dfs ((head . head) es) S.empty g in reachable == (fromList . concat) es else False toArray :: Int -> [[Int]] -> Array Int [Int] toArray n es = runST $ do g <- newArray (0, n-1) [] :: ST s (STArray s Int [Int]) forM_ es $ \[x, y] -> do readArray g x >>= writeArray g x . (y:) readArray g y >>= writeArray g y . (x:) freeze g dfs :: Int -> Set Int -> Array Int [Int] -> Set Int dfs u vis g = foldl' f (insert u vis) (g ! u) where f :: Set Int -> Int -> Set Int f vis v | member v vis = vis | otherwise = dfs v vis g