#905968 (Fortran) No.2427 Tree Distance Two

• 問題: No.2427 Tree Distance Two
• ユーザー: osada-yum
• 提出日時: 2023-08-18 23:27:44
• 言語: Fortran (gFortran 13.2.0)
• 結果: AC
• 実行時間: 409 ms / 2,000 ms
• コード長: 13,294 bytes
• コンパイル時間: 1,688 ms
• コンパイル使用メモリ: 37,760 KB
• 実行使用メモリ: 34,944 KB
• 最終ジャッジ日時: 2024-11-28 10:47:58
• 合計ジャッジ時間: 9,423 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	393 ms; 33,024 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	409 ms; 33,024 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	322 ms; 34,056 KB
testcase_08	AC	339 ms; 34,944 KB
testcase_09	AC	328 ms; 34,048 KB
testcase_10	AC	341 ms; 34,336 KB
testcase_11	AC	345 ms; 34,464 KB
testcase_12	AC	366 ms; 33,652 KB
testcase_13	AC	384 ms; 33,332 KB
testcase_14	AC	273 ms; 32,868 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	9 ms; 5,248 KB
testcase_21	AC	9 ms; 5,248 KB
testcase_22	AC	3 ms; 5,248 KB
testcase_23	AC	3 ms; 5,248 KB
testcase_24	AC	8 ms; 5,248 KB
testcase_25	AC	81 ms; 10,480 KB
testcase_26	AC	247 ms; 21,376 KB
testcase_27	AC	165 ms; 15,988 KB
testcase_28	AC	373 ms; 30,976 KB
testcase_29	AC	312 ms; 27,392 KB
testcase_30	AC	220 ms; 20,740 KB
testcase_31	AC	125 ms; 14,320 KB
testcase_32	AC	209 ms; 20,608 KB
testcase_33	AC	188 ms; 18,688 KB
testcase_34	AC	51 ms; 7,552 KB

ソースコード

module unwrapped_vector_m
  use, intrinsic :: iso_fortran_env
  implicit none
  private
  public :: unwrapped_vector_int32
  type :: unwrapped_vector_int32
     private
     integer(int32), allocatable, public :: arr_(:)
     integer(int32) :: size_ = 0, capa_ = 0
   contains
     procedure, pass :: init      => init_unwrapped_vector_int32
     procedure, pass :: push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32
     generic         :: push_back => push_back_unwrapped_vector_int32, push_back_array_unwrapped_vector_int32
     procedure, pass :: pop_back  => pop_back_unwrapped_vector_int32
     procedure, pass :: back      => back_unwrapped_vector_int32
     procedure, pass :: size      => size_unwrapped_vector_int32
     procedure, pass :: resize    => resize_unwrapped_vector_int32
     procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int32
  end type unwrapped_vector_int32
  interface unwrapped_vector_int32
     module procedure :: construct_unwrapped_vector_int32_by_size, &
          construct_unwrapped_vector_int32_by_arr, &
          construct_unwrapped_vector_int32_by_init_val
  end interface unwrapped_vector_int32

  public :: unwrapped_vector_int64
  type :: unwrapped_vector_int64
     private
     integer(int64), allocatable, public :: arr_(:)
     integer(int32) :: size_ = 0, capa_ = 0
   contains
     procedure, pass :: init      => init_unwrapped_vector_int64
     procedure, pass :: push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64
     generic         :: push_back => push_back_unwrapped_vector_int64, push_back_array_unwrapped_vector_int64
     procedure, pass :: pop_back  => pop_back_unwrapped_vector_int64
     procedure, pass :: back      => back_unwrapped_vector_int64
     procedure, pass :: size      => size_unwrapped_vector_int64
     procedure, pass :: resize    => resize_unwrapped_vector_int64
     procedure, pass :: lower_bound => lower_bound_unwrapped_vector_int64
  end type unwrapped_vector_int64
  interface unwrapped_vector_int64
     module procedure :: construct_unwrapped_vector_int64_by_size, &
          construct_unwrapped_vector_int64_by_arr, &
          construct_unwrapped_vector_int64_by_init_val
  end interface unwrapped_vector_int64
contains
  !> construct_unwrapped_vector_int32_by_size: Construct unwrapped_vector_int32 by the size, the initial values is unknown.
  impure function construct_unwrapped_vector_int32_by_size(size) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: size
    call res%init(size)
  end function construct_unwrapped_vector_int32_by_size
  !> construct_unwrapped_vector_int32_by_arr: Construct unwrapped_vector_int32 by the array of integer(int32).
  impure function construct_unwrapped_vector_int32_by_arr(arr) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: arr(:)
    integer(int32) :: n
    n = size(arr)
    call res%init(n)
    res%arr_(1:n) = arr(1:n)
  end function construct_unwrapped_vector_int32_by_arr
  !> construct_unwrapped_vector_int32_by_init_val: Construct unwrapped_vector_int32 by size and the initial values.
  impure function construct_unwrapped_vector_int32_by_init_val(size, val) result(res)
    type(unwrapped_vector_int32) :: res
    integer(int32), intent(in) :: size
    integer(int32), intent(in) :: val
    call res%init(size)
    res%arr_(1:size) = val
  end function construct_unwrapped_vector_int32_by_init_val
  !> init_unwrapped_vector_int32: Initialize the unwrapped_vector_int32 by size.
  subroutine init_unwrapped_vector_int32(this, n)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: n
    if (.not. allocated(this%arr_)) then
       allocate(this%arr_(n))
       this%size_ = n
       this%capa_ = n
    end if
  end subroutine init_unwrapped_vector_int32
  !> push_back_unwrapped_vector_int32: Insert value to the tail of elements of the unwrapped_vector_int32.
  subroutine push_back_unwrapped_vector_int32(this, val)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: val
    if (.not. allocated(this%arr_)) call this%resize(0)
    if (this%size_ == this%capa_) then
       call this%resize(2*this%capa_)
    end if
    this%size_ = this%size_ + 1
    this%arr_(this%size_) = val
  end subroutine push_back_unwrapped_vector_int32
  !> push_back_array_unwrapped_vector_int32: Insert elemeents of array to the tail of elements of the unwrapped_vector_int32.
  subroutine push_back_array_unwrapped_vector_int32(this, arr)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: arr(:)
    integer(int32) :: s
    s = size(arr)
    if (.not. allocated(this%arr_)) call this%init(s)
    if (this%size_ + s > this%capa_) then
       call this%resize(this%size_ + s)
    end if
    this%arr_(this%size_+1:this%size_+s) = arr(:)
    this%size_ = this%size_ + s
  end subroutine push_back_array_unwrapped_vector_int32
  !> pop_back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.
  integer(int32) function pop_back_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(inout) :: this
    pop_back_unwrapped_vector_int32 = this%arr_(this%size_)
    this%size_ = this%size_ - 1
  end function pop_back_unwrapped_vector_int32
  !> back_unwrapped_vector_int32: Delete the value in the end of arr_(:) of the unwrapped_vector_int32 and return it.
  integer(int32) function back_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(inout) :: this
    back_unwrapped_vector_int32 = this%arr_(this%size_)
  end function back_unwrapped_vector_int32
  !> size_vector_int32: Return current size of the unwrapped_vector_int32.
  pure integer(int32) function size_unwrapped_vector_int32(this)
    class(unwrapped_vector_int32), intent(in) :: this
    size_unwrapped_vector_int32 = this%size_
  end function size_unwrapped_vector_int32
  !> resize_unwrapped_vector_int32: Shrink or expand arr_(:) of the unwrapped_vector_int32.
  subroutine resize_unwrapped_vector_int32(this, resize)
    class(unwrapped_vector_int32), intent(inout) :: this
    integer(int32), intent(in) :: resize
    integer(int32), allocatable :: tmp(:)
    if (resize < 1) then
       this%size_ = 0
       allocate(tmp(1))
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = 1
    else
       if (this%capa_ == resize) return
       allocate(tmp(resize))
       this%size_ = min(this%size_, resize)
       tmp(1:this%size_) = this%arr_(1:this%size_)
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = resize
    end if
  end subroutine resize_unwrapped_vector_int32
  !> lower_bound_vector_int32: Return the minimum index that is higher than or equal to .
  integer(int32) function lower_bound_unwrapped_vector_int32(this, val)
    class(unwrapped_vector_int32), intent(in) :: this
    integer(int32), intent(in) :: val
    integer(int32) :: p, q, r
    p = 1
    r = this%size_
    if (this%arr_(r) < val) then
       lower_bound_unwrapped_vector_int32 = r + 1
       return
    end if
    do
       q = (p+r)/2
       if (p + 1 > r) exit
       if (this%arr_(q) >= val) then
          r = q
       else
          p = q+1
       end if
    end do
    lower_bound_unwrapped_vector_int32 = q
  end function lower_bound_unwrapped_vector_int32

  !> construct_unwrapped_vector_int64_by_size: Construct unwrapped_vector_int64 by the size, the initial values is unknown.
  impure function construct_unwrapped_vector_int64_by_size(size) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int32), intent(in) :: size
    call res%init(size)
  end function construct_unwrapped_vector_int64_by_size
  !> construct_unwrapped_vector_int64_by_arr: Construct unwrapped_vector_int64 by the array of integer(int64).
  impure function construct_unwrapped_vector_int64_by_arr(arr) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int64), intent(in) :: arr(:)
    integer(int32) :: n
    n = size(arr)
    call res%init(n)
    res%arr_(1:n) = arr(1:n)
  end function construct_unwrapped_vector_int64_by_arr
  !> construct_unwrapped_vector_int64_by_init_val: Construct unwrapped_vector_int64 by size and the initial values.
  impure function construct_unwrapped_vector_int64_by_init_val(size, val) result(res)
    type(unwrapped_vector_int64) :: res
    integer(int32), intent(in) :: size
    integer(int64), intent(in) :: val
    call res%init(size)
    res%arr_(1:size) = val
  end function construct_unwrapped_vector_int64_by_init_val
  !> init_unwrapped_vector_int64: Initialize the unwrapped_vector_int64 by size.
  subroutine init_unwrapped_vector_int64(this, n)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int32), intent(in) :: n
    if (.not. allocated(this%arr_)) then
       allocate(this%arr_(n))
       this%size_ = n
       this%capa_ = n
    end if
  end subroutine init_unwrapped_vector_int64
  !> push_back_unwrapped_vector_int64: Insert value to the tail of elements of the unwrapped_vector_int64.
  subroutine push_back_unwrapped_vector_int64(this, val)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int64), intent(in) :: val
    if (.not. allocated(this%arr_)) call this%resize(0)
    if (this%size_ == this%capa_) then
       call this%resize(2*this%capa_)
    end if
    this%size_ = this%size_ + 1
    this%arr_(this%size_) = val
  end subroutine push_back_unwrapped_vector_int64
  !> push_back_array_unwrapped_vector_int64: Insert elemeents of array to the tail of elements of the unwrapped_vector_int64.
  subroutine push_back_array_unwrapped_vector_int64(this, arr)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int64), intent(in) :: arr(:)
    integer(int32) :: s
    s = size(arr)
    if (.not. allocated(this%arr_)) call this%init(s)
    if (this%size_ + s > this%capa_) then
       call this%resize(this%size_ + s)
    end if
    this%arr_(this%size_+1:this%size_+s) = arr(:)
    this%size_ = this%size_ + s
  end subroutine push_back_array_unwrapped_vector_int64
  !> pop_back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.
  integer(int64) function pop_back_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(inout) :: this
    pop_back_unwrapped_vector_int64 = this%arr_(this%size_)
    this%size_ = this%size_ - 1
  end function pop_back_unwrapped_vector_int64
  !> back_unwrapped_vector_int64: Delete the value in the end of arr_(:) of the unwrapped_vector_int64 and return it.
  integer(int64) function back_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(inout) :: this
    back_unwrapped_vector_int64 = this%arr_(this%size_)
  end function back_unwrapped_vector_int64
  !> size_vector_int64: Return current size of the unwrapped_vector_int64.
  pure integer(int32) function size_unwrapped_vector_int64(this)
    class(unwrapped_vector_int64), intent(in) :: this
    size_unwrapped_vector_int64 = this%size_
  end function size_unwrapped_vector_int64
  !> resize_unwrapped_vector_int64: Shrink or expand arr_(:) of the unwrapped_vector_int64.
  subroutine resize_unwrapped_vector_int64(this, resize)
    class(unwrapped_vector_int64), intent(inout) :: this
    integer(int32), intent(in) :: resize
    integer(int64), allocatable :: tmp(:)
    if (resize < 1) then
       this%size_ = 0
       allocate(tmp(1))
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = 1
    else
       if (this%capa_ == resize) return
       allocate(tmp(resize))
       this%size_ = min(this%size_, resize)
       tmp(1:this%size_) = this%arr_(1:this%size_)
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = resize
    end if
  end subroutine resize_unwrapped_vector_int64
  !> lower_bound_vector_int64: Return the minimum index that is higher than or equal to .
  integer(int32) function lower_bound_unwrapped_vector_int64(this, val)
    class(unwrapped_vector_int64), intent(in) :: this
    integer(int64), intent(in) :: val
    integer(int32) :: p, q, r
    p = 1
    r = this%size_
    if (this%arr_(r) < val) then
       lower_bound_unwrapped_vector_int64 = r + 1
       return
    end if
    do
       q = (p+r)/2
       if (p + 1 > r) exit
       if (this%arr_(q) >= val) then
          r = q
       else
          p = q+1
       end if
    end do
    lower_bound_unwrapped_vector_int64 = q
  end function lower_bound_unwrapped_vector_int64
end module unwrapped_vector_m

program yukicoder_2427
  use, intrinsic :: iso_fortran_env
  use unwrapped_vector_m, only: &
       vec_i32 => unwrapped_vector_int32
  implicit none
  integer(int32) :: n, u, v, next_v, cnts
  type(vec_i32), allocatable :: g(:)
  logical, allocatable :: visited(:)
  integer(int32) :: i
  read(input_unit, *) n
  allocate(g(n))
  do i = 1, n - 1
     read(input_unit, *) u, v
     call g(u)%push_back(v)
     call g(v)%push_back(u)
  end do
  allocate(visited(n), source = .false.)
  do v = 1, n
     cnts = 0_int32
     do i = 1, g(v)%size()
        next_v = g(v)%arr_(i)
        cnts = cnts + g(next_v)%size() - 1
     end do
     write(output_unit, '(i0)') cnts
  end do
end program yukicoder_2427