結果

問題 No.1266 7 Colors
ユーザー rutilicus
提出日時 2020-10-25 12:45:40
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 1,725 ms / 3,000 ms
コード長 2,865 bytes
コンパイル時間 21,949 ms
コンパイル使用メモリ 464,704 KB
実行使用メモリ 130,856 KB
最終ジャッジ日時 2024-07-21 20:50:39
合計ジャッジ時間 53,996 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:111:25: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
                builder.appendln(uf.sizeOf(x * 7))
                        ^

ソースコード

diff #
プレゼンテーションモードにする

class UnionFind(n: Int) {
private val parent = IntArray(n) { -1 }
private val rank = IntArray(n)
private val size = IntArray(n) { 1 }
private var numTree = n
fun find(x: Int): Int {
if (parent[x] == -1) {
return x
} else {
parent[x] = find(parent[x])
return parent[x]
}
}
fun isSame(x: Int, y: Int): Boolean {
return find(x) == find(y)
}
fun getSize(): Int {
return numTree
}
fun sizeOf(x: Int): Int {
return size[find(x)]
}
fun rankOf(x: Int): Int {
return rank[find(x)]
}
fun unite(x: Int, y: Int) {
val parentX = find(x)
val parentY = find(y)
if (parentX == parentY) {
return
}
numTree--
if (rank[parentX] < rank[parentY]) {
parent[parentX] = parentY
size[parentY] += size[parentX]
} else {
parent[parentY] = parentX
size[parentX] += size[parentY]
if (rank[parentX] == rank[parentY]) {
rank[parentX]++
}
}
}
}
fun main() {
val builder = StringBuilder()
//
val (n, m, q) = readInputLine().split(" ").map { it.toInt() }
val nodes = Array(n) { BooleanArray(7) }
val edges = Array(n) { mutableListOf<Int>() }
val uf = UnionFind(n * 7)
for (i in 0 until n) {
val s = readInputLine()
for ((j, c) in s.withIndex()) {
if (c == '1') {
nodes[i][j] = true
}
}
for (j in 0 until 7) {
if (nodes[i][j] && nodes[i][(j + 1) % 7]) {
uf.unite(i * 7 + j, i * 7 + (j + 1) % 7)
}
}
}
repeat(m) {
val (u, v) = readInputLine().split(" ").map { it.toInt() - 1 }
edges[u].add(v)
edges[v].add(u)
for (i in 0 until 7) {
if (nodes[u][i] && nodes[v][i]) {
uf.unite(u * 7 + i, v * 7 + i)
}
}
}
repeat(q) {
val (type, x, y) = readInputLine().split(" ").map { it.toInt() - 1 }
when(type) {
0 -> {
nodes[x][y] = true
for (e in edges[x]) {
if (nodes[x][y] && nodes[e][y]) {
uf.unite(x * 7 + y, e * 7 + y)
}
}
for (i in 0 until 7) {
if (nodes[x][i] && nodes[x][(i + 1) % 7]) {
uf.unite(x * 7 + i, x * 7 + (i + 1) % 7)
}
}
}
else -> {
builder.appendln(uf.sizeOf(x * 7))
}
}
}
print(builder.toString())
}
fun readInputLine(): String {
return readLine()!!
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0