Submission #64166949

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))
get_root <- function(uf, x) {
  path <- numeric()
  while (uf[x] > 0) {
    path[[length(path) + 1]] <- x
    x <- uf[x]
  }
  list(root = x, path = path)
}
HW <- as.integer(split(rin()))
H <- HW[1]
W <- HW[2]
uf <- numeric(H * W)
painted <- matrix(0, H, W)
Q <- as.integer(rin())
di <- c(-1, 0, 1, 0)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

options(scipen = 100, digits = 10)
conn <- file("stdin", open = "r")
rin <- function(n = 1) readLines(conn, n = n)
split <- function(str, split = " ") unlist(strsplit(str, split = split))

get_root <- function(uf, x) {
  path <- numeric()
  while (uf[x] > 0) {
    path[[length(path) + 1]] <- x
    x <- uf[x]
  }
  list(root = x, path = path)
}

HW <- as.integer(split(rin()))
H <- HW[1]
W <- HW[2]
uf <- numeric(H * W)
painted <- matrix(0, H, W)
Q <- as.integer(rin())
di <- c(-1, 0, 1, 0)
dj <- c(0, 1, 0, -1)
ans <- vector("logical", 0)
for (. in seq_len(Q)) {
  q <- as.integer(split(rin()))
  if (q[1] == 1) {
    i <- q[2]
    j <- q[3]
    painted[i, j] <- 1
    for (k in 1:4) {
      .i <- i + di[k]
      .j <- j + dj[k]
      if ((0 < .i) && (.i <= H) && (0 < .j) && (.j <= W) && painted[.i, .j]) {
        x <- ( i - 1) * W +  j
        y <- (.i - 1) * W + .j
        rx <- get_root(uf, x)
        uf[rx$path] <- rx$root
        ry <- get_root(uf, y)
        uf[ry$path] <- ry$root
        # unite x & y
        if (rx$root == ry$root)
          next
        if (uf[rx$root] < uf[ry$root]) {
          rz <- ry
          ry <- rx
          rx <- rz
        }
        uf[rx$root] <- uf[rx$root] + uf[ry$root] - 1
        uf[ry$root] <- rx$root
      }
    }
  } else {
    i <- q[2]
    j <- q[3]
    .i <- q[4]
    .j <- q[5]
    res <- FALSE
    if (painted[i, j] && painted[.i, .j]) {
      x <- ( i - 1) * W +  j
      y <- (.i - 1) * W + .j
      rx <- get_root(uf, x)
      uf[rx$path] <- rx$root
      ry <- get_root(uf, y)
      uf[ry$path] <- ry$root
      # united
      if (rx$root == ry$root) {
        res <- TRUE
      }
    }
    ans[[length(ans) + 1]] <- res
  }
}
ans <- paste0(ifelse(ans, "Yes", "No"), collapse = "\n")
cat(ans)

Submission Info

Judge Result