Submission #5025356

---

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
;;;
;;; Bron-Kerbosch-Tomita
;;;

(defun find-max-clique (neighbors)
  "NEIGHBORS[i] is the bitset indicating the neighbors of the vertex I."
  (declare #.OPT
           ((simple-array (unsigned-byte 16) (*)) neighbors))
  (let ((n (length neighbors))
        (result-set 0)
        (result-size 0))
    (declare ((unsigned-byte 62) result-set result-size))
    (labels ((tzcount (x)
               (- (integer-length (logand x (- x))) 1))
             (recur (r p x)
               (declare ((unsigned-byte 62) r p x))
               (if (zerop p)
                   (when (zerop x)
                     (let ((size (logcount r)))
                       (when (> size result-size)
                         (setf result-set r
                               result-size size))))
                   (let ((pivot 0)
                         (max -1)
                         (p-or-x (logior p x)))
                     ;; Choose the pivot vertex in P∪X as the vertex with the
                     ;; highest number of neighbors in P
                     (loop for u from (tzcount p-or-x) below (integer-length p-or-x)
                           do (when (logbitp u p-or-x)
                                (let ((num-neighbors (logcount (logand p (aref neighbors u)))))
                                  (when (> num-neighbors max)
                                    (setf pivot u
                                          max num-neighbors)))))
                     (let ((pivot-neighbors (logandc2 p (aref neighbors pivot))))
                       (unless (zerop pivot-neighbors)
                         (loop for v from (tzcount pivot-neighbors) below (integer-length pivot-neighbors)
                               do (when (logbitp v p)
                                    (recur (dpb 1 (byte 1 v) r)
                                           (logand p (aref neighbors v))
                                           (logand x (aref neighbors v)))
                                    (setf (ldb (byte 1 v) p) 0
                                          (ldb (byte 1 v) x) 1)))))))))
      (declare (inline tzcount))
      (recur 0 (- (ash 1 n) 1) 0)
      result-set)))

(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

(defun main ()
  (let* ((n (read))
         (m (read))
         (graph (make-array n :element-type 'uint16 :initial-element 0)))
    (declare (uint16 n m))
    (dotimes (_ m)
      (let ((x (- (read) 1))
            (y (- (read) 1)))
        (setf (ldb (byte 1 y) (aref graph x)) 1
              (ldb (byte 1 x) (aref graph y)) 1)))
    (println (logcount (find-max-clique graph)))))

#-swank(main)

Submission Info

Judge Result