AtCoder Beginner Contest D - Ki Difficulty: 923
Dieses Thema, nebenstehende Liste
Probleme wie eine erweiterte Version der zuvor gelösten * AtCoder ABC168 D Adjacent List, gelöst mit Ruby, Python und networkx *.
Dieses Mal wird der Zählerwert von der Wurzel des Baums an den Scheitelpunkt gesendet. Bereiten Sie also ein Array für den Zähler vor und übergeben Sie den Zählerwert, indem Sie von der Wurzel zum Scheitelpunkt suchen. 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]
Hier wird der Wert des Zählers übergeben. 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
Die Verwendung von "stdin" beschleunigt die Ausführung erheblich.
| Ruby | Python | Python (stdin) | PyPy | PyPy (stdin) | |
|---|---|---|---|---|---|
| Codelänge(Byte) | 442 | 681 | 736 | 681 | 736 |
| Ausführungszeit(ms) | 802 | 1734 | 1044 | 1959 | 864 |
| Erinnerung(KB) | 25468 | 53008 | 53040 | 105164 | 91852 |
Recommended Posts