#P9319. [EGOI 2022] Social Engineering / 社会工程

    ID: 10450 远端评测题 5000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2022交互题Special JudgeO2优化EGOI(欧洲/女生)

[EGOI 2022] Social Engineering / 社会工程

题目背景

Day 1 Problem C.

题面译自 EGOI2022 socialengineering

本题是一道 Grader 交互题。

本题只支持 C++ 提交,提交时不需要包含 socialengineering.h 头文件,但需要在代码中包含 GetMoveMakeMove 函数的声明(见【交互方式】部分)。

请使用 C++14、C++17 等语言,而不是 C++14 (GCC 9),因为一些未知原因这个语言下 SPJ 会 CE。

感谢

https://www.luogu.com.cn/user/556366
互库和测试数据。

题目描述

一个社交网络是一个 nnmm 边的无向连通图组成,其中每个点代表一个人,如果两个人之间有边相连,他们就是朋友。

玛丽亚是这个社交网络的成员。她喜欢以各种事情挑战她的朋友。这意味着,她首先执行一些简单的任务,然后挑战她的一个朋友做同样的事情。这个朋友随后会挑战他的一个朋友,而被挑战的朋友会接着挑战他的另一个朋友,以此类推。同一个人可能会被挑战多次,但每一个无序朋友对最多进行一次挑战。(一旦 A 挑战了 B,那么 A 和 B 都不能再次挑战对方。)换句话说,挑战可以看作图中的一条路径,其中一条边至多经过一次。

如果轮到一个人,而他又不能挑战任何朋友,那么这个人就输了。挑战总是由玛丽亚开始,她很少输。现在其他 n1n-1 人决定合作,以使玛丽亚输掉下一次挑战,请你帮助他们完成目标。


交互方式

你必须实现一个函数:

void SocialEngineering(int n, int m, vector<pair<int,int>> edges);

这个函数在 nnmm 边的图上玩该游戏。这个函数会被交互库调用恰好一次。列表 edges 包含恰好 mm 对整数 (u,v)(u,v),表示有一条连接点 uu 和点 vv 的边。节点编号从 11nn。玛丽亚永远是节点 11。你的函数可以调用以下函数:

int GetMove();

这个函数应当在玛丽亚的回合被调用,例如游戏的最开始。如果你在不是玛丽亚的回合调用这个函数,你会 WA。这个函数可以返回以下值之一:

  • 一个整数 vv,其中 2vn2\le v\le n。这意味着玛丽亚挑战编号为 vv 的人。保证这一步一定合法。
  • 00,如果玛丽亚认输。当玛丽亚没有合法操作时,她就会认输。当这发生时,你的程序应当使 SocialEngineering 函数返回,然后你会 AC。
void MakeMove(int v);

这个函数应当在不是玛丽亚的回合被调用。这意味着当前回合的人挑战第 vv 个人。如果这一步不合法,或者在玛丽亚的回合调用这个函数,你会 WA。如果在游戏开始时,玛丽亚有必胜策略,你的程序应当在第一次调用 GetMove() 前使 SocialEngineering 函数返回,然后你会 AC。

输入格式

见【交互方式】部分。

输出格式

见【交互方式】部分。

提示

样例交互过程 11

你的操作 交互库的操作 解释说明
SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}}) SocialEngineering 被调用,参数为一个 5566 边的图。
GetMove() 返回 44 玛丽亚挑战第 44 个人。
MakeMove(2) 44 个人挑战第 22 个人。
MakeMove(5) 22 个人挑战第 55 个人。
MakeMove(1) 55 个人挑战玛丽亚。
GetMove() 返回 00 玛丽亚没有合法操作,所以她认输。
返回 你赢了游戏,应当使 SocialEngineering 函数返回。

样例交互过程 22

你的操作 交互库的操作 解释说明
SocialEngineering(5, 1, {{1,2}}) SocialEngineering 被调用,参数为一个 2211 边的图。
返回 玛丽亚有必胜策略,你的程序应当在未调用 GetMove() 前使 SocialEngineering 函数返回以认输。

数据范围

对于全部数据,2n2×1052\le n\le 2\times 10^51m4×1051\le m\le 4\times 10^5。保证图连通,每对无序点对至多作为边出现一次,每条边连接两个不同节点。

当玛丽亚有必胜策略时,她会完美地执行必胜策略。如果她没有必胜策略,她会试图以各种聪明的手段引诱你的程序犯错误。除子任务三外,只有当玛丽亚没有合法操作时,她才会认输。

  • 子任务一(1515 分):n,m10n,m\le 10
  • 子任务二(1515 分):除玛丽亚外,每个人至多有 22 个朋友。
  • 子任务三(2020 分):除非玛丽亚有必胜策略,否则她会立即认输。
  • 子任务四(2525 分):n,m100n,m\le 100
  • 子任务五(2525 分):无特殊限制。

感谢

https://www.luogu.com.cn/user/556366
互库和测试数据。