Solving with Ruby and Python AtCoder ABC138 D Adjacency list

Introduction

This theme

AtCoder Beginner Contest D - Ki Difficulty: 923

This theme, adjacency list

Problems such as the advanced version of * Solved with Ruby, Python and networkx AtCoder ABC168 D Adjacency List *.

This time, the counter value is sent from the root of the tree to the apex, so prepare an array for the counter and pass the counter value by searching from the root to the apex. Ruby

ruby.rb


n, q = gets.split.map(&:to_i)
a = Array.new(n){[]}
n.pred.times do
    x, y = gets.split.map(&:to_i)
    a[x - 1] << y - 1
    a[y - 1] << x - 1
end
p = Array.new(n){0}
q.times do |i|
  x, y = gets.split.map(&:to_i)
  p[x - 1] += y
end
c = Array.new(n){0}
c[0] = 1
que = []
que << 0
while que.size > 0
  e = que.shift
  a[e].each do |i|
    next if c[i] > 0
    c[i] = 1
    p[i] += p[e]
    que << i
  end
end
puts p

index.rb


    p[i] += p[e]

The value of the counter is passed here. Python

python.py


from sys import stdin

def main():
    from collections import deque
    input = stdin.readline
    n, q = map(int, input().split())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = map(int, input().split())
        a[x - 1].append(y - 1)
        a[y - 1].append(x - 1)
    p = [0] * n
    for i in range(q):
        x, y = map(int, input().split())
        p[x - 1] += y
    c = [0] * n
    c[0] = 1
    que = deque([])
    que.append(0)
    while len(que) > 0:
        e = que.popleft()
        for i in a[e]:
            if c[i] > 0:
                continue
            c[i] = 1
            p[i] += p[e]
            que.append(i)
    for i in range(n):
        print(p[i])
main()

stdin.py


from sys import stdin
    input = stdin.readline

Using stdin will significantly increase the execution time.

Ruby Python Python (stdin) PyPy PyPy (stdin)
Code length(Byte) 442 681 736 681 736
Execution time(ms) 802 1734 1044 1959 864
memory(KB) 25468 53008 53040 105164 91852

Summary

Recommended Posts

Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solve AtCoder ABC168 with python (A ~ D)
Solving with Ruby AtCoder ABC110 C String Manipulation
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solve AtCoder ABC166 with python
AtCoder ABC 182 Python (A ~ D)
Solve AtCoder ABC 186 with Python
AtCoder ARC080 D simulation solved in Ruby and Python
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
Scraping with Node, Ruby and Python
Solve ABC166 A ~ D with Python
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
AtCoder ABC168 A case expression solved in Ruby and Python
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Solve AtCoder 167 with python
Ruby, Python and map
Python and Ruby split
Initialize list with python
Try to operate DB with Python and visualize with d3
Comparison of CoffeeScript with JavaScript, Python and Ruby grammar
Version control of Node, Ruby and Python with anyenv
AtCoder ABC 177 Python (A ~ E)
Programming with Python and Tkinter
Encryption and decryption with Python
Light blue with AtCoder @Python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Python and hardware-Using RS232C with Python-
Python on Ruby and angry Ruby on Python