白駿-会社文化(14267)
Dynamic Programming
質問する
英仙会社には良い文化があります.上司は直属の部下を褒め、部下は直属の部下を褒め続けます.つまり、上司がトップの上司を褒めると、部下のすべての部下が褒められるということです.
すべての称賛には称賛の度合いを表す数値があり、この数値も部下から称賛されている.
直属の上司と直属の部下の関係、褒め言葉のメッセージを送る場合は、それぞれがどれだけ褒められたかを印刷してください.
入力
1行目は会社の社員数n名、最初に褒めた回数mを示しています.社員番号は1番からn番までです.(2 ≤ n, m ≤ 100,000)
2行目はn人の従業員のトップ上司の番号を示した.トップの上司の番号は自分の番号より小さく、最終的には社長です.1番なら上司がいないので-1と入力します.
次のm行は、直属の上司から褒められた社員番号i、褒められた数値wです.(2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)
社長は上司がいないので、ほめられません.
しゅつりょく
1番からn番までの社員はほめられる程度を書いてください.
タイムアウト
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n, m = map(int, input().split())
graph1 = list(map(int, input().split()))
# 부하 배열
graph2 = [[] for i in range(n)]
a = []
dp = [0] * n
def DFS(node, score):
k = graph2[node - 1]
if k:
for i in range(len(k)):
dp[k[i] - 1] += score
DFS(k[i], score)
for i in range(1, len(graph1)):
graph2[graph1[i] - 1].append(i + 1)
for i in range(m):
x, y = map(int, input().split())
a.append([x, y])
for i in range(len(a)):
node = a[i][0] # 시작 노드
score = a[i][1]
dp[node - 1] += score
DFS(node, score)
print(*dp)
import sys
sys.setrecursionlimit(1000000)
def nextStep(transmission, nextTaker): # transmission: 전달되는 칭찬, nextTaker: 전달받을 직원
transmission += praise[nextTaker]
# 현재 nextTaker가 전달받은 칭찬 + 현재 nextTaker가 자신의 부하전달해줄 칭찬 누적
# => 다음 부하직원에게 넘길 준비
praise[nextTaker] += (transmission - praise[nextTaker])
# 현재 nextTaker가 직속 상사로부터 받은 칭찬을 누적
for i in sub[nextTaker]:
nextStep(transmission, i)
input = sys.stdin.readline
n, m = map(int, input().split())
boss = list(map(int, input().split()))
sub = [[] for i in range(n)]
praise = [0 for i in range(n)]
for i in range(n):
boss[i] -= 1
# 부하직원 배열인 sub를 편하게 만들기 위한 작업
for j in range(m):
i, w = map(int,input().split())
praise[i - 1] += w
for i in range(n):
if boss[i] != -2:
sub[boss[i]].append(i)
nextStep(0,0)
for i in praise:
print(i)
Reference
この問題について(白駿-会社文化(14267)), 我々は、より多くの情報をここで見つけました https://velog.io/@skkfea07/백준-회사-문화14267テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol