結果

問題 No.1103 Directed Length Sum
ユーザー sansaquasansaqua
提出日時 2020-07-03 22:02:53
言語 Common Lisp
(sbcl 2.3.8)
結果
RE  
実行時間 -
コード長 5,742 bytes
コンパイル時間 1,806 ms
コンパイル使用メモリ 50,252 KB
実行使用メモリ 46,644 KB
最終ジャッジ日時 2024-09-17 01:04:33
合計ジャッジ時間 2,346 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 17 SEP 2024 01:04:28 AM):

; file: /home/judge/data/code/Main.lisp
; in: DEFUN MAIN
;     (INCF SIZE (AREF SIZES CHILD))
; --> THE 
; ==>
;   (+ (AREF SIZES CHILD) SIZE)
; 
; 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.

;     (- (READ-FIXNUM) 1)
; 
; note: forced to do GENERIC-- (cost 10)
;       unable to do inline fixnum arithmetic (cost 1) because:
;       The first argument is a NUMBER, not a FIXNUM.
;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL).
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a NUMBER, not a FIXNUM.
;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL).
;       etc.
; 
; note: forced to do GENERIC-- (cost 10)
;       unable to do inline fixnum arithmetic (cost 1) because:
;       The first argument is a NUMBER, not a FIXNUM.
;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL).
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a NUMBER, not a FIXNUM.
;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &OPTIONAL).
;       etc.

; file: /home/judge/data/code/Main.lisp
; in: DEFUN MAIN
;     (READ-FIXNUM)
; 
; caught STYLE-WARNING:
;   undefined function: COMMON-LISP-USER::READ-FIXNUM
; 
; compilation unit finished
;   Undefined fu

ソースコード

diff #

(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
;;;
;;; 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
")))
0