結果

問題 No.1103 Directed Length Sum
ユーザー sansaquasansaqua
提出日時 2020-07-04 00:24:02
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 666 ms / 3,000 ms
コード長 7,441 bytes
コンパイル時間 1,520 ms
コンパイル使用メモリ 52,276 KB
実行使用メモリ 140,488 KB
最終ジャッジ日時 2024-09-17 05:16:36
合計ジャッジ時間 7,830 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
外部呼び出し有り
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
33,060 KB
testcase_01 AC 18 ms
32,932 KB
testcase_02 AC 340 ms
140,488 KB
testcase_03 AC 213 ms
64,548 KB
testcase_04 AC 315 ms
52,248 KB
testcase_05 AC 666 ms
60,340 KB
testcase_06 AC 209 ms
41,900 KB
testcase_07 AC 51 ms
33,588 KB
testcase_08 AC 72 ms
33,724 KB
testcase_09 AC 39 ms
31,488 KB
testcase_10 AC 95 ms
35,500 KB
testcase_11 AC 370 ms
49,972 KB
testcase_12 AC 191 ms
41,648 KB
testcase_13 AC 92 ms
39,568 KB
testcase_14 AC 30 ms
31,484 KB
testcase_15 AC 139 ms
39,856 KB
testcase_16 AC 396 ms
51,888 KB
testcase_17 AC 424 ms
52,144 KB
testcase_18 AC 86 ms
37,684 KB
testcase_19 AC 344 ms
50,220 KB
testcase_20 AC 39 ms
35,564 KB
testcase_21 AC 58 ms
33,724 KB
testcase_22 AC 305 ms
50,072 KB
testcase_23 AC 142 ms
39,856 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 17 SEP 2024 05:16:28 AM):

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.067

ソースコード

diff #

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx opt
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

;;;
;;; Arithmetic operations with static modulus
;;;

;; FIXME: Currently MOD* and MOD+ doesn't apply MOD when the number of
;; parameters is one.
(defmacro define-mod-operations (divisor)
  `(progn
     (defun mod* (&rest args)
       (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

     (defun mod+ (&rest args)
       (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))

     #+sbcl
     (eval-when (:compile-toplevel :load-toplevel :execute)
       (locally (declare (muffle-conditions warning))
         (sb-c:define-source-transform mod* (&rest args)
           (if (null args)
               1
               (reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args)))
         (sb-c:define-source-transform mod+ (&rest args)
           (if (null args)
               0
               (reduce (lambda (x y) `(mod (+ ,x ,y) ,',divisor)) args)))))

     (define-modify-macro incfmod (delta)
       (lambda (x y) (mod (+ x y) ,divisor)))

     (define-modify-macro decfmod (delta)
       (lambda (x y) (mod (- x y) ,divisor)))

     (define-modify-macro mulfmod (multiplier)
       (lambda (x y) (mod (* x y) ,divisor)))))


(in-package :cl-user)

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(define-mod-operations +mod+)
(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (graph (make-array n :element-type 'list :initial-element nil))
         (dp (make-array n :element-type 'uint31 :initial-element 0))
         (sizes (make-array n :element-type 'uint31 :initial-element 0))
         (marked (make-array n :element-type 'bit :initial-element 0)))
    (dotimes (i (- n 1))
      (let ((a (- (read-fixnum) 1))
            (b (- (read-fixnum) 1)))
        (setf (aref marked b) 1)
        (push b (aref graph a))))
    (let ((root (position 0 marked)))
      (sb-int:named-let dfs ((v root))
        (let ((size 1))
          (declare (uint31 size))
          (dolist (child (aref graph v))
            (dfs child)
            (incf size (aref sizes child)))
          (setf (aref sizes v) size)))
      (sb-int:named-let dfs ((v root))
        (let ((value 0))
          (declare (uint62 value))
          (dolist (child (aref graph v))
            (dfs child)
            (incf value (aref sizes child))
            (incf value (aref dp child)))
          (setf (aref dp v) (mod value +mod+))))
      (println (mod (loop for x across dp sum x of-type uint62) +mod+)))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3
1 2
1 3
"
    "2
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5
2 1
1 3
1 4
3 5
"
    "13
")))
0