[AMPPZ2013] Bytehattan

Luogu

IDLGP10665

Time1000ms

Memory512MB

DifficultyP6

图论2013并查集O2优化ICPC

比特哈顿镇有 $n\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。 ## Input 第一行包含两个正整数 $n,k(2\leq n\leq 1500,1\leq k\leq 2n(n-1))$，表示网格图的大小以及操作的个数。接下来 $k$ 行，每行包含两条信息，每条信息包含两个正整数 $a,b(1\leq a,b\leq n)$ 以及一个字符 $c$（$c$ 为 `N` 或者 `E`）。如果 $c$ 为 `N`，表示删除 $(a,b)$ 到 $(a,b+1)$ 这条边；如果 $c$ 为 `E`，表示删除 $(a,b)$ 到 $(a+1,b)$ 这条边。数据进行了加密，对于每个操作，如果上一个询问回答为 TAK 或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。数据保证每条边最多被删除一次。 ## Output 输出 $k$ 行，对于每个询问，如果仍然连通，输出 TAK，否则输出 NIE。 [samples] ## Note 数据保证，$2\leq n\leq 1500$，$1\leq k\leq 2n(n-1)$，$1\leq a,b\leq n$。

Samples

Input #1

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

Output #1

TAK
TAK
NIE
NIE

API Response (JSON)

{
  "problem": {
    "name": "[AMPPZ2013] Bytehattan",
    "description": {
      "content": "比特哈顿镇有 $n\\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。 有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10665"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "比特哈顿镇有 $n\\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。\n\n有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。\n\n## Input\n\n第一行包含两个正整数 $n,k(2\\leq n\\leq 1500,1\\leq k\\leq 2n(n-1))$，表示网格图的大小以及操作的个数。\n\n接下来 $k$ 行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments