提出 #42138506
ソースコード 拡げる
func main() {
var scanner = Scanner()
let N = scanner.read(Int.self)
let M = scanner.read(Int.self)
let K = scanner.read(Int.self)
var G = [[Int]](repeating: [], count: N)
for _ in 0 ..< M {
let a = scanner.read(Int.self) - 1
let b = scanner.read(Int.self) - 1
G[a].append(b)
G[b].append(a)
}
var E = [[Int]](repeating: [], count: N + 1)
for i in 0 ..< K {
let p = scanner.read(Int.self) - 1
let h = scanner.read(Int.self)
E[h].append(p)
}
var queue = [Int]()
var inQueue = [Bool](repeating: false, count: N)
var visited = [Bool](repeating: false, count: N)
for h in (0 ... N).reversed() {
var nextQueue = [Int]()
for u in queue {
inQueue[u] = false
for v in G[u] {
if !visited[v] {
visited[v] = true
inQueue[v] = true
nextQueue.append(v)
}
}
}
queue = nextQueue
for p in E[h] {
if !visited[p] && !inQueue[p] {
queue.append(p)
inQueue[p] = true
visited[p] = true
}
}
}
var answer = [Int]()
for i in 0 ..< N {
if visited[i] {
answer.append(i)
}
}
print(answer.count)
print(answer.map { $0 + 1 }.map(\.description).joined(separator: " "))
}
main()
struct Scanner {
private var tokens = [String]()
private var index = 0
mutating func read<T>(_ type: T.Type) -> T where T: LosslessStringConvertible {
T(read())!
}
mutating func read<T>(_ type: T.Type, count n: Int) -> [T] where T: LosslessStringConvertible {
(0 ..< n).map { _ in read(type) }
}
private mutating func read() -> String {
while tokens.count == index {
tokens = readLine()!.split(separator: " ").map(\.description)
index = 0
}
defer {
index += 1
}
return tokens[index]
}
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | E - Art Gallery on Graph |
| ユーザ | semisagi |
| 言語 | Swift (5.2.1) |
| 得点 | 475 |
| コード長 | 1891 Byte |
| 結果 | AC |
| 実行時間 | 901 ms |
| メモリ | 27964 KiB |
コンパイルエラー
./Main.swift:14:7: warning: immutable value 'i' was never used; consider replacing with '_' or removing it
for i in 0 ..< K {
^
_
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 475 / 475 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
| All | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 02_tree_00.txt, 02_tree_01.txt, 03_path_00.txt, 03_path_01.txt, 04_perfect_00.txt, 05_corner_1_00.txt, 05_corner_1_01.txt, 05_corner_1_02.txt, 05_corner_1_03.txt, 05_corner_1_04.txt, 05_corner_1_05.txt, 06_star_00.txt, 06_star_01.txt, 07_n_m_k_max_00.txt, 07_n_m_k_max_01.txt, 07_n_m_k_max_02.txt, 07_n_m_k_max_03.txt, 07_n_m_k_max_04.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| 00_sample_00.txt | AC | 42 ms | 8100 KiB |
| 00_sample_01.txt | AC | 6 ms | 7960 KiB |
| 00_sample_02.txt | AC | 8 ms | 8180 KiB |
| 01_random_00.txt | AC | 95 ms | 12596 KiB |
| 01_random_01.txt | AC | 15 ms | 10700 KiB |
| 01_random_02.txt | AC | 524 ms | 22012 KiB |
| 01_random_03.txt | AC | 542 ms | 22564 KiB |
| 01_random_04.txt | AC | 103 ms | 11892 KiB |
| 01_random_05.txt | AC | 402 ms | 13072 KiB |
| 01_random_06.txt | AC | 428 ms | 18476 KiB |
| 01_random_07.txt | AC | 463 ms | 21828 KiB |
| 01_random_08.txt | AC | 20 ms | 10152 KiB |
| 01_random_09.txt | AC | 16 ms | 10472 KiB |
| 01_random_10.txt | AC | 529 ms | 21916 KiB |
| 01_random_11.txt | AC | 558 ms | 22896 KiB |
| 02_tree_00.txt | AC | 560 ms | 24628 KiB |
| 02_tree_01.txt | AC | 467 ms | 23180 KiB |
| 03_path_00.txt | AC | 473 ms | 22876 KiB |
| 03_path_01.txt | AC | 433 ms | 23120 KiB |
| 04_perfect_00.txt | AC | 326 ms | 12072 KiB |
| 05_corner_1_00.txt | AC | 726 ms | 27604 KiB |
| 05_corner_1_01.txt | AC | 729 ms | 27648 KiB |
| 05_corner_1_02.txt | AC | 784 ms | 27940 KiB |
| 05_corner_1_03.txt | AC | 779 ms | 27964 KiB |
| 05_corner_1_04.txt | AC | 723 ms | 26836 KiB |
| 05_corner_1_05.txt | AC | 730 ms | 26840 KiB |
| 06_star_00.txt | AC | 774 ms | 25956 KiB |
| 06_star_01.txt | AC | 805 ms | 25928 KiB |
| 07_n_m_k_max_00.txt | AC | 880 ms | 24932 KiB |
| 07_n_m_k_max_01.txt | AC | 875 ms | 24656 KiB |
| 07_n_m_k_max_02.txt | AC | 876 ms | 24568 KiB |
| 07_n_m_k_max_03.txt | AC | 868 ms | 24792 KiB |
| 07_n_m_k_max_04.txt | AC | 901 ms | 24828 KiB |