当前位置: 首页 > news >正文

题解:换乘旅行

换乘旅行

题目描述

小明来到了一座著名的旅游城市,这座城市有一个包含\(n\)个站点的公共交通网络。该网络的运行方式非常独特。每个站点\(i\)都有一个按顺序排列的摆渡车出发队列。每辆摆渡车都有一个固定的、预先设定的目的地站点。一位旅客的行程如下:每当他到达一个站点(无论是起点还是中途换乘),他都必须搭乘该站点队列中最靠前的一辆摆渡车,这辆车会将他送到其目的地,然后不再运行。到达新站点后,他会继续按相同规则搭乘下一辆车。当旅客到达一个没有任何待出发车辆的站点时,他的旅程就结束了,该站点即为他的最终目的地。这些站点排成一排,从左到右依次编号为\(1\)\(n\)。小明想要知道,对于每一个站点,如果从它出发,最终会到达哪里。

输入格式

从文件\(travel.in\)中读入数据。
第一行包含一个整数\(n\),表示站点的数量。
接下来\(n\)行,第\(i\)行描述了第\(i\)个站点的摆渡车队列信息。
• 行首是一个整数\(k_i\),表示站点 i 的队列中有\(k_i\)辆摆渡车。
• 随后是\(k_i\)个整数\(d_{i,1},d_{i,2},...,d_{i,k_i}\),按出发顺序列出了每辆车的目的地。\(d_{i,1}\)是第一辆出发的车的目标站,\(d_{i,2}\)是第二辆,以此类推。

输出格式

输出到文件\(travel.out\)中。
输出\(n\)行:
\(i\)行包含一个整数,表示从站点\(i\)开始旅行的最终站点的编号。

输入输出样例

输入 #1

3
3 1 2 2
3 3 1 2
3 1 2 1

输出 #1

1
2
2

输入 #2

5
5 1 2 4 3 4
6 1 2 5 3 3 4
6 1 1 4 4 4 2
9 3 1 4 2 3 5 5 1 2
4 4 4 1 3

输出 #2

1
1
1
1
1

子任务

对于所有数据,保证:
\(1≤n≤10^5\)
\(0≤k_i≤10^5\)
\(\sum_{i=1}^{n}k_i≤10^6\)
\(1≤d_{i,j}≤n\)

测试点 \(n\) \(\sum_{i=1}^nk_i\) 附加限制
1~4 \(≤1000\) \(≤1000\)
5~7 \(≤10^5\) \(≤10^5\) \(k_i=1\)
8~10 \(≤10^5\) \(≤10^6\)
http://www.hskmm.com/?act=detail&tid=26278

相关文章:

  • 2025企业级AI数据防泄漏指南:精准选型与核心指标全景透视
  • 感觉你是那种
  • 鲜花:不会说明你有抑郁症1
  • 【比赛记录】2025CSP-S模拟赛59
  • 使用 C 语言实现英文数字验证码识别系统
  • APlayer的配置方法和相关资料整理(已完成)
  • 详细介绍:目标检测任务的评估指标mAP50和mAP50-95
  • 一些有一定趣味性的杂题
  • 用 Haskell 实现英文数字验证码识别
  • 深入解析:Day43 Python打卡训练营
  • 用 Perl 实现验证码图像识别
  • 实用指南:【结构型模式】代理模式
  • cnblog Test
  • 云数据仓库十年架构演进与技术突破
  • 20251007 模拟测 总结
  • 2025国庆Day6
  • Claude 封杀中国后,我终于找到了平替!
  • [退役感言]You are my only one.
  • Mortal
  • python,shell,linux,bash概念的不同和对比联系 - 指南
  • 制作局域网连接打印机exe文件
  • 深入解析:linux——账号和权限的管理
  • pandoc使用
  • c#造个轮子--GIF录制工具
  • netdata
  • 关于Elment-plus的el-table组件无法通过原生JS监听scroll事件
  • arc3.2语言sort的时候报错:(sort < `(2 9 3 7 5 1)) 得写成此种:(sort > (pair (list 3 2)))
  • 噬菌体展示技术:从诺奖成果到疫苗研发,这一 “表型 - 基因型统一” 工具如何颠覆生物研究?
  • 从零开始学Flink:实时流处理实战
  • 高质量同人动画整理回顾记录的方式