AT_abc483_c.Second Choice Election
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
AtCoder Village is holding an election to choose its mayor.
There are N candidates, numbered candidate 1, candidate 2, …, candidate N.
There are M voters. The i-th voter (1≤i≤M) has candidate Ai as their first choice and candidate Bi as their second choice.
When exactly one of the candidates withdraws, each voter votes as follows.
- If the voter's first-choice candidate has not withdrawn, the voter votes for their first-choice candidate.
- If the voter's first-choice candidate has withdrawn, the voter votes for their second-choice candidate.
Among the candidates who have not withdrawn, the candidate with the most votes wins. If there are multiple such candidates, the one with the smallest number wins.
For each k=1,2,…,N, find the number of the candidate who wins when only candidate k withdraws.
AtCoder 村正在举行一场选举以选出村长。
共有 N 位候选人,编号分别为候选人 1、候选人 2、…、候选人 N。
共有 M 名选民。第 i 名选民(1≤i≤M)的第一选择是候选人 Ai,第二选择是候选人 Bi。
当恰好一位候选人退选时,每名选民的投票规则如下:
- 若该选民的第一选择候选人未退选,则该选民为其第一选择候选人投票;
- 若该选民的第一选择候选人已退选,则该选民为其第二选择候选人投票。
在所有未退选的候选人中,得票数最多的候选人当选;若存在多名候选人得票数并列最多,则编号最小者当选。
对每个 k=1,2,…,N,求出仅候选人 k 退选时的当选候选人编号。
输入格式
The input is given from Standard Input in the following format:
N M
A1 B1
A2 B2
⋮
AM BM
输入从标准输入中按以下格式给出:
N M
A1 B1
A2 B2
⋮
AM BM
输出格式
Print N lines. The i-th line should contain the number of the candidate who wins when only candidate i withdraws.
输出 N 行。第 i 行应包含仅候选人 i 退选时的获胜候选人编号。
输入输出样例
输入#1
5 6 1 3 1 3 2 1 2 1 3 4 4 2
输出#1
3 1 1 2 1
说明/提示
Sample 1 Explanation:
When only candidate 1 withdraws, the voters vote as follows.
- Voter 1's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
- Voter 2's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
- Voter 3's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
- Voter 4's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
- Voter 5's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 3.
- Voter 6's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 4.
Thus, candidate 2 receives 2 votes, candidate 3 receives 3 votes, and candidate 4 receives 1 vote, so candidate 3, who has the most votes, wins.
When each of the other candidates withdraws instead, the results are as follows.
- When only candidate 2 withdraws, candidate 1 receives 4 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the most votes, wins.
- When only candidate 3 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, and candidate 4 receives 2 votes, so candidate 1, who has the smallest number among those with the most votes, wins.
- When only candidate 4 withdraws, candidate 1 receives 2 votes, candidate 2 receives 3 votes, and candidate 3 receives 1 vote, so candidate 2, who has the most votes, wins.
- When only candidate 5 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the smallest number among those with the most votes, wins.
Thus, print 3,1,1,2,1 in this order, one per line.
Constraints
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤Ai,Bi≤N
- Ai=Bi
- All input values are integers.
样例 1 解释:
当仅有候选人 1 退选时,选民的投票情况如下:
- 选民 1 的首选候选人已退选,因此转而投票给其第二顺位候选人,即候选人 3。
- 选民 2 的首选候选人已退选,因此转而投票给其第二顺位候选人,即候选人 3。
- 选民 3 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 2。
- 选民 4 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 2。
- 选民 5 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 3。
- 选民 6 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 4。
因此,候选人 2 获得 2 票,候选人 3 获得 3 票,候选人 4 获得 1 票,得票最多的候选人 3 当选。
当其余每位候选人分别单独退选时,结果如下:
- 当仅有候选人 2 退选时,候选人 1 获得 4 票,候选人 3 获得 1 票,候选人 4 获得 1 票,因此得票最多的候选人 1 当选。
- 当仅有候选人 3 退选时,候选人 1 获得 2 票,候选人 2 获得 2 票,候选人 4 获得 2 票,因此在得票最多的候选人中编号最小者(即候选人 1)当选。
- 当仅有候选人 4 退选时,候选人 1 获得 2 票,候选人 2 获得 3 票,候选人 3 获得 1 票,因此得票最多的候选人 2 当选。
- 当仅有候选人 5 退选时,候选人 1 获得 2 票,候选人 2 获得 2 票,候选人 3 获得 1 票,候选人 4 获得 1 票,因此在得票最多的候选人中编号最小者(即候选人 1)当选。
因此,按顺序输出 3,1,1,2,1,每行一个。
约束条件
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤Ai,Bi≤N
- Ai=Bi
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?