← 返回题目列表

AtCoder · ijpc_imo

A. 国际道马尾奥林匹克运动会

中文机器翻译题面 查看原题

今天,国际信息学奥林匹克竞赛将在快速发展的K国举行。国际数学奥林匹克竞赛已经在该国举行,但当时,由于K国的失误,比赛期间,运动员乘坐的巴士是IMO[1]东道国如果有一名运动员参加两次国际信息学奥林匹克竞赛,那就太尴尬了,所以我们决定采取措施,确保没有运动员参加国际信息学奥林匹克竞赛。

K国,这块土地被用于举办国际信息奥运会。 使用 N 城市。 N 城市是 M 它们由主要道路连接,并且这些道路可以双向通过。每条道路都连接两个不同的城市,并且道路除了城市之外不会在任何点相交。另外,K国所有城市都实行数字化管理。

过去调查IMO的原因后发现,原因是司机在驾驶公交车时误读了城市号码。因此,为了减少本次比赛的误读,我们决定将城市编号按照更容易理解的顺序排列,以便在开车时更容易查看。路线上的城市数量应始终单调增加或减少。由于比赛日程尚未确定,因此必须考虑所有巴士路线。但是,不应考虑多次访问同一城市的巴士路线。满足这个条件的K国的状态将被称为“K国的好状态”。即使没有公共汽车路线,K国仍然是“K国的好状态”。

然而,城市号码不能轻易更改,因为人们对它们很熟悉。经过国会反复辩论,决定道路上两个城市之间的号码每天只能交换一次。由于距离比赛举行的时间已经不多了,所以必须在尽可能短的时间内让K-Country进入“良好状态”。

请注意,本文纯属虚构,K国并非国家队球员友好的国家。

[1] IMO 是“International Lost Olympics”的俚语,在文本中被解释为“在国际比赛中迷失”。

課題

给定城市和道路信息,通过反复交换道路两端的城市编号,计算出使任意一条简单路线具有该路线上城市编号升序或降序排列所需的最少操作次数(使K国进入“K国良好状态”所需的天数)。

具有以下参数的过程 best_swap(N,M,E) 实施 :

  • N -- 城市数量。 0 从 N-1 它们的编号最大为 。
  • M -- 道路数量。 0 从 M-1 每条道路连接两个不同的城市,每条道路的编号最大为 。 可能有多个路径具有相同的(于 14:07 添加) 每条路都不同。.
  • E ——表示道路信息的二维数组。 0 ≤ i < M 对于 ,道路 i 是一座城市 E[i][0] 和 我讨厌 E[i][1] 已连接。

best_swap(N,M,E) 实施 是所需的操作数。 必须返回最小値。如果K国无论怎么交换都无法满足条件, 必须返回 -1 。

例

例1

举个例子 N = 3, M = 2,

E = 考虑 0   2
1 2

的情况。在这种情况下,交换城市 1 和城市 2 的编号将导致“K 国的良好状态”。 best_swap(N,M,E) 实施 表示 1 。

例2

举个例子 N = 3, M = 3 考虑,

E = 考虑 0   1
1 2
0 2

的情况。在这种情况下,无论怎么交换,都有一条绕着0、2、1的路径,因此K国不可能处于“K国的良好状态”。因此, best_swap(N,M,E) 实施 表示 -1 。

例3

举个例子 N = 6, M = 8 考虑,

E = 考虑 0   1
3 2
1 2
4 5
5 2
3 0
2 4
5 4

的情况。在这种情况下也 best_swap(N,M,E) 实施 表示 -1 。

小課題

小課題 1 (10 点)

  • 1 ≤ N ≤ 1 000
  • M = N-1
  • K国拥有最简单的直线形状。任意两个城市都有一条路线连接,且道路数量相同。1一座像书一样的城市2或更少。

小課題 2 (44 点)

  • 1 ≤ N ≤ 100 000
  • M = N-1
  • K国拥有最简单的直线形状。任意两个城市都有一条路线连接,且道路数量相同。1一座像书一样的城市2或更少。

小課題 3 (46 点)

  • 1 ≤ N ≤ 100 000
  • 0 ≤ M ≤ 200 000

实施细节

制限

  • CPU时间限制:1秒
  • 内存限制:256 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹:imo/(原型: imo.zip)
  • 参赛者实现的文件:imo.cpp
  • 提交文件接口:imo.h
  • 评分程序示例:grader.cpp
  • 评分程序的示例输入:grader.in.1、grader.in.2、...
    注意:示例评分程序按以下格式读取输入。
    • 1 行目: N 的值和 M 值
    • 从第 2 行开始 M+1 线路:道路信息。换句话说, 对于0 ≤ i < M 对于 , i+2 行是 E[i][0] 和 我讨厌 E[i][1] 之间用空格分隔。
  • 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
    注意:示例评分程序按以下格式写入输出。 一个整数,即
    • best_swap(N,M,E) 实施 的返回值