Submission #3960878
Source Code Expand
(eval-when (:compile-toplevel :load-toplevel :execute)
(defparameter OPT
#+swank '(optimize (speed 3) (safety 2))
#-swank '(optimize (speed 3) (safety 0) (debug 0)))
#+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
(shadow :run)
(use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
;; BEGIN_INSERTED_CONTENTS
(defmacro bufferd-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
(let ((buffer (gensym)) (c (gensym)) (idx (gensym)))
`(let ((,buffer (load-time-value (make-string ,buffer-size
:element-type 'base-char
:initial-element ,terminate-char))))
(declare (simple-base-string ,buffer))
(loop for ,c of-type base-char =
#-swank (code-char (read-byte ,in nil #\Newline))
#+swank (read-char ,in nil #\Newline)
for ,idx from 0
until (char= ,c #\Newline)
do (setf (schar ,buffer ,idx) ,c)
finally (setf (schar ,buffer ,idx) ,terminate-char)
(return ,buffer)))))
(defmacro split-ints-and-bind (arg-lst string &body body)
(let ((pos1 (gensym "POS"))
(pos2 (gensym "POS"))
(str (gensym "STR")))
(labels ((expand (arg-lst &optional (init-pos1 t))
(if (null arg-lst)
body
`((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
(,pos2 (position #\space ,str :start ,pos1 :test #'char=))
(,(car arg-lst) (parse-integer ,str :start ,pos1 :end ,pos2)))
,@(expand (cdr arg-lst) nil))))))
`(let ((,str ,string))
(declare (string ,str))
,@(expand arg-lst)))))
(declaim (inline split-ints-into-vector))
(defun split-ints-into-vector (str dest-arr &key (offset 0) (key #'identity))
(declare ((simple-array * (*)) dest-arr)
((integer 0 #.most-positive-fixnum) offset)
(function key)
(string str))
(loop for idx from offset below (length dest-arr)
for pos1 = 0 then (1+ pos2)
for pos2 = (position #\space str :start pos1 :test #'char=)
do (setf (aref dest-arr idx)
(funcall key (parse-integer str :start pos1 :end pos2)))
finally (return dest-arr)))
(defstruct (union-find-tree
(:constructor make-union-find-tree
(size
&aux
(parents (let ((arr (make-array size :element-type '(integer 0 #.most-positive-fixnum))))
(dotimes (i size arr) (setf (aref arr i) i))))
(ranks (make-array size :element-type '(integer 0 #.most-positive-fixnum)
:initial-element 0)))))
(parents nil :type (simple-array (integer 0 #.most-positive-fixnum) (*)))
(ranks nil :type (simple-array (integer 0 #.most-positive-fixnum) (*))))
(declaim (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional)) uf-root))
(defun uf-root (x uf-tree)
"Returns the root of X."
(declare #.OPT ((integer 0 #.most-positive-fixnum) x))
(let ((parents (union-find-tree-parents uf-tree)))
(if (= x (aref parents x))
x
(setf (aref parents x)
(uf-root (aref parents x) uf-tree)))))
(declaim (inline uf-unite!))
(defun uf-unite! (x1 x2 uf-tree)
"Unites X1 and X2 destructively."
(let ((root1 (uf-root x1 uf-tree))
(root2 (uf-root x2 uf-tree))
(parents (union-find-tree-parents uf-tree))
(ranks (union-find-tree-ranks uf-tree)))
(cond ((= root1 root2) nil)
((< (aref ranks root1) (aref ranks root2))
(setf (aref parents root1) root2))
((= (aref ranks root1) (aref ranks root2))
(setf (aref parents root2) root1)
(incf (aref ranks root1)))
(t (setf (aref parents root2) root1)))))
(declaim (inline uf-connected-p))
(defun uf-connected-p (x1 x2 uf-tree)
"Checks if X1 and X2 have the same root."
(= (uf-root x1 uf-tree) (uf-root x2 uf-tree)))
(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 4 7 8 15 16 31 32 62 63 64)
(defmacro println (obj &optional (stream '*standard-output*))
`(let ((*read-default-float-format* 'double-float))
(prog1 (princ ,obj ,stream) (terpri ,stream))))
;; Hauptteil
(defun main ()
(declare #.OPT)
(let* ((n (read))
(m (read))
(seq (make-array n :element-type 'uint32))
(tree (make-union-find-tree n)))
(declare (uint32 n m)
((simple-array uint32 (*)) seq))
(split-ints-into-vector (read-line) seq :key #'1-)
(dotimes (_ m)
(split-ints-and-bind (x y) (bufferd-read-line 20)
(declare (uint32 x y))
(uf-unite! (aref seq (- x 1)) (aref seq (- y 1)) tree)))
(println
(loop for i below n
count (uf-connected-p i (aref seq i) tree)))))
#-swank(main)
Submission Info
Submission Time |
|
Task |
D - Equals |
User |
sansaqua |
Language |
Common Lisp (SBCL 1.1.14) |
Score |
400 |
Code Size |
5232 Byte |
Status |
AC |
Exec Time |
298 ms |
Memory |
33764 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
298 ms |
33764 KB |
0_001.txt |
AC |
113 ms |
20960 KB |
0_002.txt |
AC |
113 ms |
20960 KB |
0_003.txt |
AC |
113 ms |
20960 KB |
1_004.txt |
AC |
152 ms |
20964 KB |
1_005.txt |
AC |
237 ms |
29160 KB |
1_006.txt |
AC |
243 ms |
29160 KB |
1_007.txt |
AC |
114 ms |
20964 KB |
1_008.txt |
AC |
113 ms |
20964 KB |
1_009.txt |
AC |
113 ms |
20964 KB |
1_010.txt |
AC |
114 ms |
20964 KB |
1_011.txt |
AC |
113 ms |
20964 KB |
1_012.txt |
AC |
114 ms |
20964 KB |
1_013.txt |
AC |
115 ms |
20964 KB |
1_014.txt |
AC |
116 ms |
20964 KB |
1_015.txt |
AC |
114 ms |
20964 KB |
1_016.txt |
AC |
115 ms |
20964 KB |
1_017.txt |
AC |
115 ms |
20968 KB |
1_018.txt |
AC |
150 ms |
20964 KB |
1_019.txt |
AC |
182 ms |
29152 KB |
1_020.txt |
AC |
181 ms |
29156 KB |
1_021.txt |
AC |
182 ms |
29152 KB |
1_022.txt |
AC |
243 ms |
29156 KB |