結果
問題 | No.1295 木と駒 |
ユーザー | semisagi |
提出日時 | 2020-11-20 22:39:58 |
言語 | Swift (5.10.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,980 bytes |
コンパイル時間 | 1,549 ms |
コンパイル使用メモリ | 137,748 KB |
実行使用メモリ | 23,628 KB |
最終ジャッジ日時 | 2024-07-23 13:29:11 |
合計ジャッジ時間 | 5,966 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
16,032 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 8 ms
9,088 KB |
testcase_05 | WA | - |
testcase_06 | AC | 8 ms
8,960 KB |
testcase_07 | AC | 8 ms
9,088 KB |
testcase_08 | WA | - |
testcase_09 | AC | 8 ms
8,960 KB |
testcase_10 | AC | 8 ms
9,088 KB |
testcase_11 | WA | - |
testcase_12 | AC | 8 ms
8,960 KB |
testcase_13 | AC | 8 ms
9,088 KB |
testcase_14 | TLE | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
ソースコード
struct Scanner { private var elements = [String]() private var index = 0 mutating func peek() -> String { while elements.count == index { elements = readLine()!.split(separator: " ").map(String.init) index = 0 } return elements[index] } mutating func next() -> String { defer { index += 1 } return peek() } mutating func nextInt() -> Int { return Int(next())! } mutating func nextInts(_ n: Int) -> [Int] { return (0 ..< n).map { _ in nextInt() } } mutating func nextDouble() -> Double { return Double(next())! } } infix operator &&=: AssignmentPrecedence func &&= (lhs: inout Bool, rhs: Bool) { lhs = lhs && rhs } var scanner = Scanner() let N = scanner.nextInt() var G = [[Int]](repeating: [], count: N) for _ in 0 ..< N - 1 { let a = scanner.nextInt() - 1 let b = scanner.nextInt() - 1 G[a].append(b) G[b].append(a) } for i in 0 ..< N { G[i].sort() } func check(_ r: Int) -> Bool { var L = [Bool](repeating: true, count: N) var R = [Bool](repeating: true, count: N) var first = [Int](repeating: Int.max, count: N) func dfs(_ x: Int, _ p: Int?) { let children = G[x].filter { $0 != p } guard !children.isEmpty else { return } first[x] = children.first! for c in children { dfs(c, x) } L[x] &&= children.allSatisfy { L[$0] && first[$0] > x } if p != nil { R[x] &&= (children[0 ..< children.count - 1].allSatisfy { L[$0] && first[$0] > x } && R[children.last!]) || (children[1 ..< children.count].allSatisfy { L[$0] && first[$0] > x } && R[children.first!]) } else { R[x] &&= (children[0 ..< children.count - 1].allSatisfy { L[$0] && first[$0] > x } && R[children.last!]) } } dfs(r, nil) return R[r] } for i in 0 ..< N { print(check(i) ? "Yes" : "No") }