[NOISG 2019 Prelim] Lost Array

Luogu

IDLGP10733

Time1000ms

Memory1024MB

DifficultyP2

2019Special Judge构造NOISG（新加坡）

给定 $M$ 组形如 $\min (X_{A_i},X_{B_i})=C_i$ 的关系式，请构造一个长度为 $N$ 的数组 $X$，使得数组中的每个数字在 $1$ 到 $10^9$ 之间，并且该数组满足所有的关系式。题目保证数组存在。 ## Input 第一行两个整数 $N,M$。接下来 $M$ 行，每行三个数字 $A_i,B_i,C_i$。 ## Output 共一行 $N$ 个整数，代表你构造的数组 $X$。 [samples] ## Background 翻译自 [NOISG2019 Prelim B.Lost Array](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。 **本题已启用 Special Judge，满足题目条件的任何答案都将视为正确。** ## Note ### 【样例 #1 解释】显然，$\min (X_2,X_1) = \min (9,7) =7$，满足题目条件。 ### 【样例 #3 解释】原题的题面没有此样例，但测试数据有。第一个限制为 $\min (X_1,X_2) =1$，所有的条件实际上和这个限制一样。 ### 【样例 #4 解释】唯一的限制为 $\min (X_1,X_2) =123$，其余的数字可以是介于 $1$ 到 $10^9$ 之间的任何数字。 ### 【数据范围】 | $\text{Subtask}$ | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $5$ | $N=2,M=1$ | | $2$ | $6$ | $M\leq 3$ | | $3$ | $20$ | $N,M\leq 1000$ | | $4$ | $21$ | $C_i \leq 10,N \leq 5$ | | $5$ | $48$ | 无 | 对于 $100\%$ 的数据： - $1 \leq N,M \leq 10^5$ - $1 \leq A_i ,B_i \leq N$ - $A_i \neq B_i$ - $1 \leq C_i \leq 10^9$

Samples

Input #1

2 1
2 1 7

Output #1

9 7

Input #2

Output #2

3 1 4 1 5

Input #3

Output #3

1 114514

Input #4

5 1
1 2 123

Output #4

123 1000000000 3 4 26311337

API Response (JSON)

{
  "problem": {
    "name": "[NOISG 2019 Prelim] Lost Array",
    "description": {
      "content": "给定 $M$ 组形如 $\\min (X_{A_i},X_{B_i})=C_i$ 的关系式，请构造一个长度为 $N$ 的数组 $X$，使得数组中的每个数字在 $1$ 到 $10^9$ 之间，并且该数组满足所有的关系式。 题目保证数组存在。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10733"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $M$ 组形如 $\\min (X_{A_i},X_{B_i})=C_i$ 的关系式，请构造一个长度为 $N$ 的数组 $X$，使得数组中的每个数字在 $1$ 到 $10^9$ 之间，并且该数组满足所有的关系式。\n\n题目保证数组存在。\n\n## Input\n\n第一行两个整数 $N,M$。\n\n接下来 $M$ 行，每行三个数字 $A_i,B_i,C_i$。\n\n## Output\n\n共一行 $N$ 个...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments