結果
| 問題 | No.1103 Directed Length Sum |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-07-03 22:03:29 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 669 ms / 3,000 ms |
| コード長 | 7,361 bytes |
| コンパイル時間 | 1,022 ms |
| コンパイル使用メモリ | 50,732 KB |
| 実行使用メモリ | 141,148 KB |
| 最終ジャッジ日時 | 2023-10-17 02:33:45 |
| 合計ジャッジ時間 | 8,813 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 外部呼び出し有り |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 21 ms
32,900 KB |
| testcase_01 | AC | 20 ms
32,900 KB |
| testcase_02 | AC | 337 ms
141,148 KB |
| testcase_03 | AC | 202 ms
64,628 KB |
| testcase_04 | AC | 366 ms
52,340 KB |
| testcase_05 | AC | 669 ms
64,620 KB |
| testcase_06 | AC | 233 ms
46,192 KB |
| testcase_07 | AC | 50 ms
35,952 KB |
| testcase_08 | AC | 74 ms
38,000 KB |
| testcase_09 | AC | 39 ms
35,940 KB |
| testcase_10 | AC | 100 ms
40,048 KB |
| testcase_11 | AC | 440 ms
52,340 KB |
| testcase_12 | AC | 246 ms
46,192 KB |
| testcase_13 | AC | 105 ms
40,048 KB |
| testcase_14 | AC | 34 ms
35,876 KB |
| testcase_15 | AC | 177 ms
42,096 KB |
| testcase_16 | AC | 485 ms
56,436 KB |
| testcase_17 | AC | 526 ms
56,436 KB |
| testcase_18 | AC | 105 ms
40,048 KB |
| testcase_19 | AC | 453 ms
54,388 KB |
| testcase_20 | AC | 42 ms
35,920 KB |
| testcase_21 | AC | 66 ms
37,996 KB |
| testcase_22 | AC | 356 ms
50,292 KB |
| testcase_23 | AC | 186 ms
44,144 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 16 OCT 2023 05:33:36 PM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAIN ; (INCF SIZE (AREF SIZES CHILD)) ; --> THE ; ==> ; (+ (AREF SIZES CHILD) SIZE) ; ; note: unable to ; optimize ; due to type uncertainty: ; The second argument is a NUMBER, not a SINGLE-FLOAT. ; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT &REST ; T). ; ; note: unable to ; optimize ; due to type uncertainty: ; The second argument is a NUMBER, not a DOUBLE-FLOAT. ; ; note: unable to ; optimize ; due to type uncertainty: ; The second argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT). ; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES ; (COMPLEX SINGLE-FLOAT) ; &REST T). ; ; note: unable to ; optimize ; due to type uncertainty: ; The second argument is a NUMBER, not a (COMPLEX DOUBLE-FLOAT). ; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES ; (COMPLEX DOUBLE-FLOAT) ; &REST T). ; ; note: forced to do GENERIC-+ (cost 10) ; unable to do inline fixnum arithmetic (cost 2) because: ; The second argument is a NUMBER, not a FIXNUM. ; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL). ; unable to do inline (unsigned-byte 64) arithmetic (cost 4) because: ; The second argument is a NUMBER, not a (UNSIGNED-BYTE 64). ; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES ; (UNSIGNED-BYTE 64) ; &OPTIONAL). ; etc. ; ; compilation unit finished ; printed 5 notes ; wrote /home/judge/data/code/Main.fasl ; compilation finishe
ソースコード
#-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"
(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))
(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 (reduce #'+ dp) +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
")))