[COCI 2023/2024 #4] Putovanje

Luogu

IDLGP10231

Time2000ms

Memory512MB

DifficultyP6

2023广度优先搜索 BFSCOCI（克罗地亚）bitset

Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。 Malnar 先生像以往一样预订了其中一个城市最贵的酒店，然后开始规划他的旅程。为了方便规划，他记录了从酒店到每个城市的最短路径长度。由于对他期待已久的假期感到兴奋，Malnar 先生完全忘记了酒店位于哪个城市。他当然不想错过这次旅行，所以他请你确定酒店可能位于哪些城市。 ## Input 第一行两个整数 $n$ 和 $m\ (1\le n\le 5\cdot 10^4,n-1\le m\le 10^5)$，分别表示城市和道路的数量。接下来 $m$ 行，每行两个整数 $u_i,v_i\ (1\le u_i,v_i\le n,u_i\neq v_i)$，表示城市 $u_i$ 和 $v_i$ 之间有一条道路。任意两城市之间最多只有一条道路。最后一行有 $n$ 个整数，第 $i$ 个整数 $d_i\ (-1\le d_i<n)$ 表示从城市 $i$ 到酒店所在城市的路径长度，如果 Malnar 先生没有记录这个值，则为 $-1$。 ## Output 第一行输出酒店可能位于多少个城市。第二行输出酒店可能位于的城市编号，**按升序输出**。 [samples] ## Background **译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T4「[Putovanje](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」** ## Note ### 样例解释 1 从城市 $4$ 到城市 $1$ 的路径长度为 $2$，到城市 $7$ 的路径长度为 $3$。因此，城市 $4$ 满足两个条件，酒店可以位于那里。同样的情况也适用于城市 $6$。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :----------------------------------------------: | :--: | | $1$ | $m+1=n\le 5\ 000$，对于所有 $i$ 满足 $u_i+1=v_i$ | $10$ | | $2$ | 对于所有 $i>1$ 满足 $d_i=-1$ | $20$ | | $3$ | $n,m\le 5\ 000$ | $35$ | | $4$ | 无附加限制 | $45$ |

Samples

Input #1

7 6
1 2
1 3
3 4
3 5
3 6
5 7
2 -1 -1 -1 -1 -1 3

Output #1

2
4 6

Input #2

6 6
1 2
2 3
3 4
4 5
5 6
6 1
2 -1 -1 1 -1 -1

Output #2

2
3 5

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2023/2024 #4] Putovanje",
    "description": {
      "content": "Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。 Malnar 先生像以往一样预订了其中一个城市",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10231"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Malnar 先生终于迎来了他的年假。他决定要去的国家可以表示为 $n$ 个城市和 $m$ 条双向连接它们的道路。每条道路的长度相同，并且可以通过这些道路从任何一个城市到达另一个城市。从城市 $a$ 到城市 $b$ 的路径被定义为一系列道路，满足从城市 $a$ 开始，按照该序列依次遍历道路，最终到达城市 $b$。路径的长度定义为该路径上的道路数量。\n\nMalnar 先生像以往一样预订了其中一个城市...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments