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
AC × 1
AC × 19
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