AtCoder Beginner Contest D - Ki Difficulty: 923
Ce thème, liste adjacente
Problèmes tels qu'une version avancée de la * liste d'adjacence AtCoder ABC168 D résolue avec Ruby, Python et networkx *.
Cette fois, la valeur du compteur est envoyée de la racine de l'arbre à l'apex, alors préparez un tableau pour le compteur et transmettez la valeur du compteur en recherchant de la racine à l'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]
La valeur du compteur est transmise ici. 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
L'utilisation de stdin accélérera considérablement l'exécution.
| Ruby | Python | Python (stdin) | PyPy | PyPy (stdin) | |
|---|---|---|---|---|---|
| Longueur du code(Byte) | 442 | 681 | 736 | 681 | 736 |
| Temps d'exécution(ms) | 802 | 1734 | 1044 | 1959 | 864 |
| Mémoire(KB) | 25468 | 53008 | 53040 | 105164 | 91852 |
Recommended Posts