Submission #451750
Source Code Expand
import scala.collection.mutable.PriorityQueue
import scala.annotation.tailrec
package net.pushl {
package number {
// Prime (Prime.scala)
// Number (Number.scala)
}
package string {
// RollingHash (RollingHash.scala)
}
package geometry {
// Point
// Segment
// Line
}
package datastructure {
class UnionFindTree(val n: Int) {
// if data[i] is less than 0, i is root and -data[i] is the size of tree
// else, data[i] is parent of i
private[this] final val data = Array.fill(n)(-1)
private def isRoot(k: Int) = data(k) < 0
@tailrec
private def getRoot(k: Int, log: List[Int] = List[Int]()) : Int =
if(isRoot(k)) {log.foreach(data(_) = k); k}
else getRoot(data(k),k :: log)
def getGroupSize(k: Int) : Int = -data(getRoot(k))
def same (a: Int, b: Int) : Boolean = getRoot(a) == getRoot(b)
def unite(a: Int, b: Int) : Boolean = {
val x = getRoot(a)
val y = getRoot(b)
if(x != y){
// connect lower to higher
val (f,t) = if(getGroupSize(x) > getGroupSize(y)) (x,y)
else (y,x)
data(t) += data(f)
data(f) = t
true
}else
false
}
}
object UnionFindTree {
def apply(n: Int) = if(n < 0) sys.error("Size of unionfind should be greater than or equal to 0")
else new UnionFindTree(n)
}
}
package io {
import java.io.{BufferedReader, PrintWriter, PrintStream, PushbackReader}
class MyConsole(val in: BufferedReader, val _out: PrintStream,
val _err: PrintStream) {
// PrintWriter do not flush automatically
val out = new PrintWriter(_out,false)
// If argument is null, there are ambiguous which function will be called
def print(obj: Any) = out.print(if(obj == null) "null" else obj.toString)
def println() = out.println
def println(obj: Any) = out.println(obj)
def printf(text: String, args: Any*) = out.printf(text.format(args : _*))
// NOTE: YOU MUST FLUSH BEFORE END OF MAIN
def flush() = out.flush
def nextInt() : Int = nextLong().toInt
def nextLong() : Long = {
if(!goNextValuable())
throw new NoSuchElementException("Reading long failed")
else{
val is_minus = peek() == '-'
@tailrec
def readLong(next: Int, cur: Long) : Long = {
if(isSpaceOrControl(next)){
if(is_minus) -cur
else cur
}else{
if('0' <= next && next <= '9')
readLong(readWithoutCheckingPeeked(), cur*10 + next-'0')
else
throw new NumberFormatException(s"readLong found strange byte $next")
}
}
readLong(read(),0)
}
}
def nextString() : String = {
if(!goNextValuable())
throw new NoSuchElementException("Reading String failed")
else {
val builder = new StringBuilder
@tailrec
def appendCode(next: Int) : String = {
if(isSpaceOrControl(next)){
builder.toString
}else{
builder.append(next.toChar)
appendCode(read())
}
}
appendCode(read())
}
}
// helpers
// private var peeked: Option[Int] = None
// private def read() =
// peeked match {
// case None => in.read()
// case Some(a) => { peeked = None; a }
// }
// private def readWithoutCheckingPeeked() = in.read()
// private def peek() =
// peeked match {
// case None => {
// val res = in.read()
// peeked = Some(res)
// res
// }
// case Some(a) => a
// }
private var peeked: Int = -2
private def read() =
if(peeked == -2) in.read()
else {val p = peeked; peeked = -2; p }
private def readWithoutCheckingPeeked() = in.read()
private def peek() =
if(peeked == -2) {
val res = in.read()
peeked = res
res
}else{
peeked
}
private def isThereReadable() = peek() != -1
// XXX: this limits c is ASCII?
private def isSpaceOrControl(c: Int) = c <= 32 || c == 127
@tailrec
private def goNextNotSpaceNorControl() : Unit = {
if(isSpaceOrControl(peek())) {
read()
goNextNotSpaceNorControl()
}else {}
}
private def goNextValuable() = {
goNextNotSpaceNorControl()
isThereReadable()
}
}
}
}
import net.pushl.io.MyConsole
object Main {
def main(args: Array[String]) : Unit = {
val console = new MyConsole(Console.in, Console.out, Console.err)
val solver = new Solver(console)
solver.main()
console.flush()
}
}
import net.pushl.datastructure.UnionFindTree
class Solver(val stdio: MyConsole){
import stdio._ // shadow Console.~
def main() = {
// val (n,q) = readLine.splitToIntTuple2
// val out = new java.io.PrintWriter(Console.out)
val n,q = nextLong().toInt
val uf = UnionFindTree(n)
(1 to q).foreach(_ => {
val p,a,b = nextLong().toInt
// readLine.splitToIntTuple3
p match {
case 0 => uf.unite(a,b)
case 1 => println(if(uf.same(a,b)) "Yes" else "No")
// case 1 => println(if(uf.same(a,b)) "Yes" else "No")
case _ => sys.error("no such query: " + p)
}
})
}
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
tomoki |
Language |
Scala (2.11.5) |
Score |
100 |
Code Size |
6056 Byte |
Status |
AC |
Exec Time |
1573 ms |
Memory |
59536 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_01.txt |
All |
00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01.txt |
AC |
1115 ms |
47196 KB |
subtask_01_01.txt |
AC |
1408 ms |
49732 KB |
subtask_01_02.txt |
AC |
1141 ms |
47464 KB |
subtask_01_03.txt |
AC |
1363 ms |
49756 KB |
subtask_01_04.txt |
AC |
1495 ms |
49816 KB |
subtask_01_05.txt |
AC |
1195 ms |
48152 KB |
subtask_01_06.txt |
AC |
1271 ms |
48856 KB |
subtask_01_07.txt |
AC |
1363 ms |
49524 KB |
subtask_01_08.txt |
AC |
1472 ms |
50300 KB |
subtask_01_09.txt |
AC |
1122 ms |
47212 KB |
subtask_01_10.txt |
AC |
1147 ms |
47772 KB |
subtask_01_11.txt |
AC |
1394 ms |
49760 KB |
subtask_01_12.txt |
AC |
1487 ms |
50172 KB |
subtask_01_13.txt |
AC |
1388 ms |
50136 KB |
subtask_01_14.txt |
AC |
1142 ms |
47456 KB |
subtask_01_15.txt |
AC |
1373 ms |
49308 KB |
subtask_01_16.txt |
AC |
1461 ms |
50260 KB |
subtask_01_17.txt |
AC |
1549 ms |
59536 KB |
subtask_01_18.txt |
AC |
1573 ms |
59104 KB |