Submission #4608658


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 buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
  "Note that the returned string will be reused."
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let ((,buffer (load-time-value (make-string ,buffer-size
                                                  :element-type 'base-char))))
       (declare (simple-base-string ,buffer))
       (loop for ,character of-type base-char =
                #-swank (code-char (read-byte ,in nil #.(char-code #\Newline)))
                #+swank (read-char ,in nil #\Newline)
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,terminate-char))
                     (return (values ,buffer ,idx))))))

(defmacro split-ints-bind (vars string &body body)
  (let ((position (gensym))
        (s (gensym)))
    (labels ((expand (vars &optional init-pos)
               (if (null vars)
                   body
                   `((multiple-value-bind (,(car vars) ,position)
                         (parse-integer ,s :start ,(or init-pos position)
                                           :junk-allowed t)
                       ,@(when (null (cdr vars)) `((declare (ignore ,position))))
                       ,@(expand (cdr vars)))))))
      `(let ((,s ,string))
         (declare (string ,s))
         ,@(expand vars 0)))))

(declaim (inline split-ints-into-vector))
(defun split-ints-into-vector (string dest-vector &key (offset 0) (key #'identity))
  (declare (string string)
           (function key)
           ((array * (*)) dest-vector)
           ((integer 0 #.most-positive-fixnum) offset))
  (loop with position = 0
        for idx from offset below (length dest-vector)
        do (setf (values (aref dest-vector idx) position)
                 (parse-integer string :start position :junk-allowed t))
           (setf (aref dest-vector idx) (funcall key (aref dest-vector idx)))
        finally (return dest-vector)))

(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)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; 0<=s_i<=p_i (i = 0, ..., n-1)
;; 0<=t_i<=q_i (i = 0, ..., n-1)
;; a_k <= s_(x_k)+t_(y_k) <= b_k (k = 0, ..., m-1)

;; t'_(y_k) := -t_(y_k).

;; 0<=s_i<=p_i (i = 0, ..., n-1)
;; -q_i<=t'_i<=0 (i = 0, ..., n-1)
;; a_k <= s_(x_k)-t'_(y_k) <= b_k (k = 0, ..., m-1)

;; I: start point
;; s_i (t'_i) be the minimal distance from I to the vertex i (n+i).
;; 0-s_i <= 0 (edge from vertex i to I with cost 0)
;; s_i-0 <= p_i (I -> i with cost p_i)
;; 0-t'_i <= q_i (i+n -> I with cost -q_i)
;; t'_i-0 <= 0 (I -> i+n with cost 0)
;; s_(x_k)-t'_(y_k) <= b_k (n+y_k -> x_k with cost b_k)
;; t'_(y_k)-s_(x_k) <= -a_k (x_k -> n+y_k with cost -a_k)

;; This program is feasible iff there is no negative cycle passing through I.
(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (m (read))
         (ps (make-array n :element-type 'uint31))
         (qs (make-array n :element-type 'uint31))
         (size (1+ (* 2 n)))
         ;; (to . cost)
         (graph (make-array size :element-type 'list :initial-element nil))
         (start (- size 1))
         (table (make-array size :element-type 'fixnum :initial-element #xffffffff)))
    (declare (uint31 n m))
    (setf (aref table start) 0)
    (split-ints-into-vector (read-line) ps)
    (split-ints-into-vector (read-line) qs)
    (dotimes (i n)
      (push (cons start 0) (aref graph i))
      (push (cons i (aref ps i)) (aref graph start))
      (push (cons start (aref qs i)) (aref graph (+ i n)))
      (push (cons (+ i n) 0) (aref graph start)))
    (dotimes (k m)
      (split-ints-bind (x y a b) (buffered-read-line)
        (declare (uint15 x y)
                 (uint31 a b))
        (decf x) (decf y)
        (push (cons x b) (aref graph (+ n y)))
        (push (cons (+ n y) (- a)) (aref graph x))))
    (dotimes (_ size)
      (let (updated-p)
        (dotimes (src size)
          (let ((current-cost (aref table src)))
            (unless (= current-cost #xffffffff)
              (dolist (edge (aref graph src))
                (let ((dest (car edge))
                      (cost (+ current-cost (the int32 (cdr edge)))))
                  (when (< cost (aref table dest))
                    (setf (aref table dest) cost
                          updated-p t)))))))
        (when (< (aref table start) 0)
          (write-line "no")
          (return-from main))
        (unless updated-p
          (write-line "yes")
          (return-from main))))
    (write-line "yes")))

#-swank(main)

Submission Info

Submission Time
Task H - Asteroids2
User sansaqua
Language Common Lisp (SBCL 1.1.14)
Score 200
Code Size 5639 Byte
Status AC
Exec Time 180 ms
Memory 23016 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 41
Set Name Test Cases
All 00-sample-00, 00-sample-01, 10-small_yes-00, 10-small_yes-01, 10-small_yes-02, 10-small_yes-03, 10-small_yes-04, 10-small_yes-05, 10-small_yes-06, 10-small_yes-07, 10-small_yes-08, 20-small_disturb-00, 20-small_disturb-01, 20-small_disturb-02, 20-small_disturb-03, 20-small_disturb-04, 20-small_disturb-05, 20-small_disturb-06, 20-small_disturb-07, 20-small_disturb-08, 30-large_yes-00, 30-large_yes-01, 30-large_yes-02, 30-large_yes-03, 30-large_yes-04, 40-large_disturb-00, 40-large_disturb-01, 40-large_disturb-02, 40-large_disturb-03, 40-large_disturb-04, 40-large_disturb-05, 40-large_disturb-06, 40-large_disturb-07, 40-large_disturb-08, 40-large_disturb-09, 40-large_disturb-10, 40-large_disturb-11, 40-large_disturb-12, 40-large_disturb-13, 40-large_disturb-14, 40-large_disturb-15
Case Name Status Exec Time Memory
00-sample-00 AC 74 ms 14820 KB
00-sample-01 AC 74 ms 14816 KB
10-small_yes-00 AC 74 ms 16872 KB
10-small_yes-01 AC 74 ms 16868 KB
10-small_yes-02 AC 76 ms 16872 KB
10-small_yes-03 AC 74 ms 16872 KB
10-small_yes-04 AC 74 ms 16864 KB
10-small_yes-05 AC 74 ms 16868 KB
10-small_yes-06 AC 83 ms 16868 KB
10-small_yes-07 AC 83 ms 16868 KB
10-small_yes-08 AC 83 ms 16864 KB
20-small_disturb-00 AC 75 ms 16868 KB
20-small_disturb-01 AC 74 ms 16868 KB
20-small_disturb-02 AC 74 ms 16868 KB
20-small_disturb-03 AC 74 ms 16868 KB
20-small_disturb-04 AC 74 ms 16864 KB
20-small_disturb-05 AC 75 ms 16872 KB
20-small_disturb-06 AC 83 ms 16864 KB
20-small_disturb-07 AC 84 ms 16868 KB
20-small_disturb-08 AC 85 ms 16740 KB
30-large_yes-00 AC 177 ms 23012 KB
30-large_yes-01 AC 180 ms 23012 KB
30-large_yes-02 AC 180 ms 23008 KB
30-large_yes-03 AC 179 ms 23008 KB
30-large_yes-04 AC 178 ms 23012 KB
40-large_disturb-00 AC 172 ms 23012 KB
40-large_disturb-01 AC 172 ms 23008 KB
40-large_disturb-02 AC 172 ms 23016 KB
40-large_disturb-03 AC 172 ms 23016 KB
40-large_disturb-04 AC 172 ms 23008 KB
40-large_disturb-05 AC 171 ms 23012 KB
40-large_disturb-06 AC 173 ms 23016 KB
40-large_disturb-07 AC 172 ms 23016 KB
40-large_disturb-08 AC 172 ms 23008 KB
40-large_disturb-09 AC 173 ms 23012 KB
40-large_disturb-10 AC 172 ms 23012 KB
40-large_disturb-11 AC 173 ms 23012 KB
40-large_disturb-12 AC 173 ms 23012 KB
40-large_disturb-13 AC 175 ms 23008 KB
40-large_disturb-14 AC 173 ms 23008 KB
40-large_disturb-15 AC 172 ms 23016 KB