結果
| 問題 | No.1103 Directed Length Sum |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-07-04 00:29:35 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 497 ms / 3,000 ms |
| コード長 | 7,429 bytes |
| コンパイル時間 | 2,527 ms |
| コンパイル使用メモリ | 48,252 KB |
| 実行使用メモリ | 146,464 KB |
| 最終ジャッジ日時 | 2023-10-17 06:40:45 |
| 合計ジャッジ時間 | 5,885 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
| 外部呼び出し有り |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 19 ms
32,628 KB |
| testcase_01 | AC | 19 ms
32,628 KB |
| testcase_02 | AC | 313 ms
146,464 KB |
| testcase_03 | AC | 185 ms
68,640 KB |
| testcase_04 | AC | 241 ms
54,300 KB |
| testcase_05 | AC | 497 ms
68,640 KB |
| testcase_06 | AC | 155 ms
46,104 KB |
| testcase_07 | AC | 45 ms
37,912 KB |
| testcase_08 | AC | 61 ms
37,912 KB |
| testcase_09 | AC | 34 ms
35,848 KB |
| testcase_10 | AC | 79 ms
39,960 KB |
| testcase_11 | AC | 269 ms
56,348 KB |
| testcase_12 | AC | 156 ms
46,104 KB |
| testcase_13 | AC | 80 ms
39,960 KB |
| testcase_14 | AC | 31 ms
35,792 KB |
| testcase_15 | AC | 124 ms
44,056 KB |
| testcase_16 | AC | 315 ms
58,396 KB |
| testcase_17 | AC | 340 ms
58,396 KB |
| testcase_18 | AC | 80 ms
39,960 KB |
| testcase_19 | AC | 269 ms
56,348 KB |
| testcase_20 | AC | 39 ms
35,856 KB |
| testcase_21 | AC | 56 ms
37,908 KB |
| testcase_22 | AC | 224 ms
52,252 KB |
| testcase_23 | AC | 129 ms
44,056 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 16 OCT 2023 09:40:35 PM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.097
ソースコード
#-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 'uint62 :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) value)))
(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
")))