[POI 2004] Bra

Luogu

IDLGP8383

Time1000ms

Memory128MB

DifficultyP5

2004POI（波兰）

让我们考虑一个包含 $n$ 个门的电路。门从 $0$ 到 $n-1$ 编号，每个门都包含若干个输入和一个输出。每一个输入和输出都只可能是 $0,1,\dfrac{1}{2}$ 三种状态，每个输入都连接着某个门的输出，输入的状态就等于它连接的输出的状态值，而每个输出可能连接着任意多个输入。 $0$ 和 $1$ 是很特殊的两个门。门 $0$ 的输出永远为 $0$，门 $1$ 的输出永远为 $1$。一个门有效的输出状态条件如下: 1. 它的输入中 $0$ 的个数多于 $1$ 的个数那么输出状态为 $0$。 2. 它的输入中 $0$ 的个数等于 $1$ 的个数那么输出状态为 $\dfrac{1}{2}$。 3. 它的输入中 $0$ 的个数少于 $1$ 的个数那么输出状态为 $1$。 4. 对于门 $0$ 和 $1$，他们分别输出 $0$ 和 $1$。现在给出电路信息，请你编写一个程序，确定所有可以确定状态的门的状态分别是什么。 ## Input 第一行一个数 $n$。接下来 $n-2$ 行表示门的连接信息，第 $i$ 行描述第 $i$ 个门的输入端，一个数 $k_i$ 表示它的输入端个数，接下来 $k_i$ 个数分别表示每个输入端的门的编号。 ## Output 输出 $n$ 行，表示 $n$ 个门的输出状态。如果确定，请输出具体状态值，否则输出 $?$ 。 [samples] ## Note 对于全部数据，$2 \le n \le 10000,k_i \ge 1$，数据保证所有门的输入端总数不超过 $200000$。

Samples

Input #1

Output #1

0
1
1/2
?
?

API Response (JSON)

{
  "problem": {
    "name": "[POI 2004] Bra",
    "description": {
      "content": "让我们考虑一个包含 $n$ 个门的电路。 门从 $0$ 到 $n-1$ 编号，每个门都包含若干个输入和一个输出。 每一个输入和输出都只可能是 $0,1,\\dfrac{1}{2}$ 三种状态，每个输入都连接着某个门的输出，输入的状态就等于它连接的输出的状态值，而每个输出可能连接着任意多个输入。 $0$ 和 $1$ 是很特殊的两个门。门 $0$ 的输出永远为 $0$，门 $1$ 的输出永远为 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8383"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "让我们考虑一个包含 $n$ 个门的电路。\n\n门从 $0$ 到 $n-1$ 编号，每个门都包含若干个输入和一个输出。\n\n每一个输入和输出都只可能是 $0,1,\\dfrac{1}{2}$ 三种状态，每个输入都连接着某个门的输出，输入的状态就等于它连接的输出的状态值，而每个输出可能连接着任意多个输入。\n\n$0$ 和 $1$ 是很特殊的两个门。门 $0$ 的输出永远为 $0$，门 $1$ 的输出永远为 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments