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 |
Recommended Posts