94 lines
2.0 KiB
Swift
94 lines
2.0 KiB
Swift
import Foundation
|
|
|
|
final class FileIO {
|
|
private let buffer:[UInt8]
|
|
private var index: Int = 0
|
|
|
|
init(fileHandle: FileHandle = FileHandle.standardInput) {
|
|
|
|
buffer = Array(try! fileHandle.readToEnd()!) + [UInt8(0)]
|
|
}
|
|
|
|
@inline(__always) private func read() -> UInt8 {
|
|
defer { index += 1 }
|
|
return buffer[index]
|
|
}
|
|
|
|
@inline(__always) func readInt() -> Int {
|
|
var sum = 0
|
|
var now = read()
|
|
var isPositive = true
|
|
|
|
while now == 10 || now == 32 { now = read() }
|
|
if now == 45 { isPositive = false; now = read() }
|
|
|
|
while now >= 48, now <= 57 {
|
|
sum = sum * 10 + Int(now-48)
|
|
now = read()
|
|
}
|
|
|
|
return sum * (isPositive ? 1 : -1)
|
|
}
|
|
}
|
|
|
|
func main() {
|
|
let fp = FileIO()
|
|
|
|
let N = fp.readInt()
|
|
|
|
var next_build: [[Int]] = Array(repeating: [], count: N+1)
|
|
var build_time: [Int] = Array(repeating: 0, count: N+1)
|
|
|
|
var qu: [Int] = Array(repeating: 0, count: N+1)
|
|
var front = 0, rear = 0
|
|
|
|
var indegree: [Int] = Array(repeating: 0, count: N+1)
|
|
|
|
for n in 1...N {
|
|
build_time[n] = fp.readInt()
|
|
|
|
while true {
|
|
let m = fp.readInt()
|
|
if m == -1 {
|
|
break
|
|
}
|
|
|
|
next_build[m].append(n)
|
|
indegree[n] += 1
|
|
}
|
|
}
|
|
|
|
for n in 1...N {
|
|
if indegree[n] == 0 {
|
|
qu[rear] = n
|
|
rear += 1
|
|
}
|
|
}
|
|
|
|
var res: [Int] = []
|
|
for n in build_time {
|
|
res.append(n)
|
|
}
|
|
|
|
while front < rear {
|
|
let now = qu[front]
|
|
front += 1
|
|
|
|
for nxt in next_build[now] {
|
|
indegree[nxt] -= 1
|
|
if indegree[nxt] == 0 {
|
|
qu[rear] = nxt
|
|
rear += 1
|
|
}
|
|
|
|
res[nxt] = max(res[nxt], res[now] + build_time[nxt])
|
|
}
|
|
}
|
|
|
|
for n in 1...N {
|
|
print(res[n])
|
|
}
|
|
}
|
|
|
|
main()
|