Submission #38447491

Source Code Expand

import qualified Data.IntMap as IM

main = do
  [n,m] <- map read . words <$> getLine
  uvs <- map (map read . words) . lines <$> getContents
  let ans = abc287c n m uvs
  putStrLn $ if ans then "Yes" else "No"

abc287c :: Int -> Int -> [[Int]] -> Bool
abc287c n m uvs = n == succ m && loop newUF uvs
  where
    loop _ [] = True
    loop uf ((u:v:_):uvs) =
      case uniteUF uf u v of
        Nothing -> False
        Just uf1 -> loop uf1 uvs    

-- ふつうにUnion-Findでいけるはずだな。

type UF = IM.IntMap Int

newUF = IM.empty

getRoot :: UF -> Int -> (Int,Int)
getRoot uf i =
  case IM.lookup i uf of
    Nothing -> (i, 1)
    Just k | k < 0 -> (i, -k)
           | otherwise -> getRoot uf k

uniteUF :: UF -> Int -> Int -> Maybe UF
uniteUF uf i j
  | a == b = Nothing
  | s >= t = Just $ IM.insert a (negate $ s+t) $ IM.insert b a uf
  | True   = Just $ IM.insert b (negate $ s+t) $ IM.insert a b uf
  where
    (a,s) = getRoot uf i
    (b,t) = getRoot uf j

Submission Info

Submission Time
Task C - Path Graph?
User joetheshootingst
Language Haskell (GHC 8.8.3)
Score 300
Code Size 1017 Byte
Status WA
Exec Time 1113 ms
Memory 49324 KiB

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result

Set Name Sample All AfterContest
Score / Max Score 0 / 0 300 / 300 0 / 0
Status
AC × 3
AC × 36
AC × 1
WA × 3
Set Name Test Cases
Sample 00_example_00.txt, 00_example_01.txt, 00_example_02.txt
All 00_example_00.txt, 00_example_01.txt, 00_example_02.txt, 01_dense_00.txt, 02_path_00.txt, 02_path_01.txt, 02_path_02.txt, 02_path_03.txt, 02_path_04.txt, 02_path_05.txt, 02_path_06.txt, 02_path_07.txt, 02_path_08.txt, 02_path_09.txt, 03_paths_00.txt, 03_paths_01.txt, 03_paths_02.txt, 04_cycles_00.txt, 04_cycles_01.txt, 04_cycles_02.txt, 04_cycles_03.txt, 04_cycles_04.txt, 04_cycles_05.txt, 05_corner_00.txt, 05_corner_01.txt, 05_corner_02.txt, 05_corner_03.txt, 05_corner_04.txt, 05_corner_05.txt, 06_random_00.txt, 06_random_01.txt, 06_random_02.txt, 06_random_03.txt, 06_random_04.txt, 07_small_00.txt, 07_small_01.txt
AfterContest 08_after_contest_00.txt, 08_after_contest_01.txt, 08_after_contest_02.txt, 08_after_contest_03.txt
Case Name Status Exec Time Memory
00_example_00.txt AC 6 ms 3832 KiB
00_example_01.txt AC 2 ms 3840 KiB
00_example_02.txt AC 2 ms 3696 KiB
01_dense_00.txt AC 2 ms 3784 KiB
02_path_00.txt AC 1113 ms 49168 KiB
02_path_01.txt AC 1103 ms 49324 KiB
02_path_02.txt AC 435 ms 22080 KiB
02_path_03.txt AC 819 ms 38676 KiB
02_path_04.txt AC 437 ms 23112 KiB
02_path_05.txt AC 901 ms 41736 KiB
02_path_06.txt AC 359 ms 21052 KiB
02_path_07.txt AC 945 ms 41568 KiB
02_path_08.txt AC 419 ms 23128 KiB
02_path_09.txt AC 29 ms 6592 KiB
03_paths_00.txt AC 5 ms 3712 KiB
03_paths_01.txt AC 3 ms 3804 KiB
03_paths_02.txt AC 2 ms 3648 KiB
04_cycles_00.txt AC 3 ms 3928 KiB
04_cycles_01.txt AC 2 ms 3812 KiB
04_cycles_02.txt AC 3 ms 3800 KiB
04_cycles_03.txt AC 2 ms 3656 KiB
04_cycles_04.txt AC 4 ms 3712 KiB
04_cycles_05.txt AC 3 ms 3712 KiB
05_corner_00.txt AC 303 ms 18260 KiB
05_corner_01.txt AC 198 ms 13920 KiB
05_corner_02.txt AC 91 ms 8844 KiB
05_corner_03.txt AC 241 ms 14916 KiB
05_corner_04.txt AC 159 ms 11768 KiB
05_corner_05.txt AC 242 ms 15940 KiB
06_random_00.txt AC 2 ms 3860 KiB
06_random_01.txt AC 5 ms 3780 KiB
06_random_02.txt AC 2 ms 3832 KiB
06_random_03.txt AC 2 ms 3828 KiB
06_random_04.txt AC 2 ms 3688 KiB
07_small_00.txt AC 2 ms 3644 KiB
07_small_01.txt AC 4 ms 3812 KiB
08_after_contest_00.txt WA 835 ms 39384 KiB
08_after_contest_01.txt WA 745 ms 34376 KiB
08_after_contest_02.txt WA 45 ms 6580 KiB
08_after_contest_03.txt AC 3 ms 3940 KiB