結果
| 問題 | No.1207 グラフX |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-08-30 13:31:40 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 10,888 bytes |
| コンパイル時間 | 1,396 ms |
| コンパイル使用メモリ | 95,660 KB |
| 実行使用メモリ | 40,668 KB |
| 最終ジャッジ日時 | 2024-04-27 06:56:52 |
| 合計ジャッジ時間 | 4,447 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
| testcase_46 | RE | - |
| testcase_47 | RE | - |
| testcase_48 | RE | - |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 27 APR 2024 06:56:47 AM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAIN ; (INCFMOD RES (MOD* COST SIZE1 SIZE2)) ; ; caught STYLE-WARNING: ; undefined function: COMMON-LISP-USER::INCFMOD ; (MOD* COST SIZE1 SIZE2) ; ; caught STYLE-WARNING: ; undefined function: COMMON-LISP-USER::MOD* ; (READ-FIXNUM) ; ; caught STYLE-WARNING: ; undefined function: COMMON-LISP-USER::READ-FIXNUM ; ; compilation unit finished ; Undefined functions: ; INCFMOD MOD* READ-FIXNUM ; caught 3 STYLE-WARNING conditions ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.317
ソースコード
#-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))))
(in-package :cl-user)
(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)
(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)
(defconstant +mod+ 1000000007)
(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)))
(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
(let ((*read-default-float-format* 'double-float))
(prog1 (princ obj stream) (terpri stream))))
;; BEGIN_INSERTED_CONTENTS
;;;
;;; Minimum spanning tree (Boruvka's algorithm, O(ElogV))
;;;
;;; Reference:
;;; Ahuja, Magnanti, Orlin. Network Flows: Theory, Algorithms, and Applications.
;;;
(defpackage :cp/boruvka
(:use :cl)
(:export #:find-mst))
(in-package :cp/boruvka)
(defconstant +inf-cost+ most-positive-fixnum)
;; Here I express each connected component as a cycle with singly-linked list,
;; though Ahuja's book adopts doubly-linked list. I learned about this technique
;; in noshi91's article: http://noshi91.hatenablog.com/entry/2019/07/19/180606
;; (Japanese)
(declaim (inline find-mst)
(ftype (function * (values (simple-array fixnum (*))
(simple-array fixnum (*))
(simple-array fixnum (*))
&optional))
find-mst))
(defun find-mst (graph &key (vertex-key #'car) (cost-key #'cdr) maximize)
"Computes an MST by Boruvka's algorithm. Returns three values: a vector that
stores each cost of the edges, two vectors that store each end of the edges. If
GRAPH is not connected, this function computes MST for each connected component.
GRAPH := vector of adjacency lists
MAXIMIZE := if true, solve maximization problem instead"
(declare (vector graph))
(let* ((n (length graph))
(roots (make-array n :element-type 'fixnum))
;; next node in a connected component
(nexts (make-array n :element-type 'fixnum))
(min-costs (make-array n :element-type 'fixnum))
(min-srcs (make-array n :element-type 'fixnum))
(min-dests (make-array n :element-type 'fixnum))
(edge-count 0)
(res-costs (make-array (max 0 (- n 1)) :element-type 'fixnum))
(res-srcs (make-array (max 0 (- n 1)) :element-type 'fixnum))
(res-dests (make-array (max 0 (- n 1)) :element-type 'fixnum)))
(dotimes (i n)
(setf (aref roots i) i
(aref nexts i) i))
(labels ((%add (src dest cost)
"Adds a new edge to the (unfinished) MST."
(declare (fixnum src dest cost))
(when (> src dest) (rotatef src dest))
(setf (aref res-srcs edge-count) src
(aref res-dests edge-count) dest
(aref res-costs edge-count) (if maximize (- cost) cost)
edge-count (+ edge-count 1)))
(%merge (root1 root2)
"Merges ROOT2 into ROOT1."
(loop for v = (aref nexts root2) then (aref nexts v)
until (= v root2)
do (setf (aref roots v) root1)
finally (setf (aref roots v) root1))
;; meld two cycles
(rotatef (aref nexts root1) (aref nexts root2))))
(loop for updated = nil
while (< edge-count (- n 1))
do (fill min-costs +inf-cost+)
;; detect minimum cost edge starting from each connected component
(dotimes (u n)
(let ((root (aref roots u)))
(dolist (edge (aref graph u))
(let ((v (funcall vertex-key edge))
(cost (funcall cost-key edge)))
(declare (fixnum v cost))
(when maximize (setq cost (- cost)))
(when (and (/= root (aref roots v))
(<= cost (aref min-costs root)))
(setf (aref min-costs root) cost
(aref min-srcs root) u
(aref min-dests root) v))))))
;; merge all the pairs of connected components linked with above
;; enumerated edges
(dotimes (v n)
(let* ((root (aref roots v))
(src (aref min-srcs root))
(dest (aref min-dests root))
(cost (aref min-costs root)))
(unless (= cost +inf-cost+) ; can be true if GRAPH is not connected
(loop for root2 = (aref roots dest)
until (= root root2)
do (setq updated t)
(%add src dest cost)
(%merge root root2)
(setq src (aref min-srcs root2)
dest (aref min-dests root2)
cost (aref min-costs root2))))))
while updated)
(values (adjust-array res-costs edge-count)
(adjust-array res-srcs edge-count)
(adjust-array res-dests edge-count)))))
(defpackage :cp/mod-power
(:use :cl)
(:export #:mod-power))
(in-package :cp/mod-power)
(declaim (inline mod-power))
(defun mod-power (base power modulus)
"Returns BASE^POWER mod MODULUS. Note: 0^0 = 1.
BASE := integer
POWER, MODULUS := non-negative fixnum"
(declare ((integer 0 #.most-positive-fixnum) modulus power)
(integer base))
(let ((base (mod base modulus))
(res (mod 1 modulus)))
(declare ((integer 0 #.most-positive-fixnum) base res))
(loop while (> power 0)
when (oddp power)
do (setq res (mod (* res base) modulus))
do (setq base (mod (* base base) modulus)
power (ash power -1)))
res))
;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/mod-power :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/boruvka :cl-user))
(in-package :cl-user)
;;;
;;; Body
;;;
(defun main ()
(let* ((n (read))
(m (read))
(x (read))
(graph (make-array n :element-type 'list :initial-element nil))
(res 0))
(declare (uint31 n m x res))
(dotimes (i m)
(let ((x (- (read-fixnum) 1))
(y (- (read-fixnum) 1))
(z (read-fixnum)))
(push (cons x z) (aref graph y))
(push (cons y z) (aref graph x))))
(multiple-value-bind (zs us vs) (find-mst graph)
(dbg zs us vs)
(let ((graph (make-array n :element-type 'list :initial-element nil))
(sizes (make-array n :element-type 'uint31 :initial-element 0)))
(loop for u across us
for v across vs
for z across zs
for cost = (mod-power x z +mod+)
do (push (cons u cost) (aref graph v))
(push (cons v cost) (aref graph u)))
#>graph
(sb-int:named-let dfs ((v 0) (parent -1))
(let ((value 1))
(loop for (child . cost) in (aref graph v)
unless (= child parent)
do (dfs child v)
(incf value (aref sizes child)))
(setf (aref sizes v) value)))
#>sizes
(sb-int:named-let dfs ((v 0) (parent -1))
(loop for (child . cost) of-type (uint31 . uint31) in (aref graph v)
for size1 = (aref sizes child)
for size2 of-type uint31 = (- n size1)
unless (= child parent)
do (incfmod res (mod* cost size1 size2))
(dfs child v)))))
(println res)))
#-swank (main)
;;;
;;; Test and benchmark
;;;
#+swank
(defun get-clipbrd ()
(with-output-to-string (out)
#+os-windows (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)
#+os-unix (run-program "xsel" '("-b" "-o") :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* (or out (make-string-output-stream)))
(res (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))))))
(if out res (get-output-stream-string *standard-output*))))
#+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
(equal "8
"
(run "3 2 3
1 2 0
2 3 1
" nil)))
(it.bese.fiveam:is
(equal "2660500
"
(run "5 5 5
1 4 3
2 4 4
3 5 7
2 3 8
2 3 10
" nil)))
(it.bese.fiveam:is
(equal "524978526
"
(run "6 8 1000000
2 6 10
3 5 11
4 6 23
1 3 26
1 6 30
5 6 48
3 5 88
3 6 100
" nil))))