QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Hackable ✓

# 5364. 面国漫步

Statistics

面国是一个古老而又广阔的国家,菲斯雷斯·杨是这个国家的统治者,面民们称之为面皇。面国由 $N$ 个城市组成,城市按照 $1..N$ 编号,其中 $1$ 号城市是面国里最有面子的城市,所以面皇设定其为面国的首都,我们称之为面都。

在面皇开天辟地的时候,这个世界上是没有道路的,唯一用来连接城市的是面皇的面子:对于任何 $i\in [2,N]$,$1$ 号城市到 $i$ 号城市都有一条长度为 $2^{60}$ 的单向道路,所以从面都出发,到达任何一个普通城市都需要 $2^{60}$ 单位的时间。

然而在面国进入工业时代后,面国的居民开始发现靠面子来进行交通是非常低效的,于是面皇开始计划在面国修建一些单向道路,并将这个项目交给了建设大臣艾莉芬特来干。

每条道路可以用一个四元组 $(u,v,w,id)$ 表示,表示一条从城市 $u$ 到城市 $v$,长度为 $w$ ,修建的时间为 $id$ 的单向道路,因为面国工程能力不足,所以所有道路的修建时间都是互不相同的。

道路修建完之后,面皇会进行视察,由于是面皇亲自视察,所以这个过程非常讲究,所以是非常复杂的,你可以结合下发的 spj.cpp 来理解这一过程。

面皇手中有一张计划表 $S$,计划表上记录了若干个城市,面皇会按照计划表的顺序从头到尾去视察城市,一开始计划表上只有面都,即 $1$ 号城市。

并且面皇对于每个城市 $i$ 会记录一个值 $dis_i$,表示当前在面皇的印象中从 $1$ 号城市出发,到达城市 $i$ 的最短路。一开始 $dis_1=0$,而且由于面皇可以用面子进行交通,所以对于除了面都以外的城市 $i$,一开始有$dis_i=2^{60}$。

当面皇视察城市 $x$ 时,面皇会按照修建时间从小到大遍历所有以 $x$ 为起点的边 $(x,y,w)$,并且检查城市 $y$ 的最短路是否可以更新,如果可以更新(即 $dis_y>dis_x+w$),那么面皇会令 $dis_y=w+dis_x$,并且检查一下根据计划表后面还会不会视察城市 $y$,如果暂时视察不到的话,就将城市 $y$ 加入计划表的末尾。

(在另一个世界中,这种视察方法被称为 SPFA。)

然而面皇的爸爸"鸭子的王"曾经说过:"关于SPFA,他已经死了",所以面皇对SPFA感到非常忌讳,于是面皇命令艾莉芬特代替他去视察,并把最后产生的计划表交上来。

然而艾莉芬特也有事情要做,于是他随便造了一张计划表上去,现在面皇想拜托你确认下,是否存在任何一种道路的建设方法,使得最后的计划表跟艾莉芬特交上来的相同

输入格式

第一行两个正整数 $N$,$K$,分别表示城市个数和艾莉芬特提交的计划表的长度。

第二行 $K$ 个正整数,按照从头到尾的顺序给出了计划表的内容。

输出格式

如果不存在一种道路建设的方法,使得最后的计划表和艾莉芬特给出的相同,则在第一行输出字符串"YouAreFake!" (不含双引号,注意大小写),否则在第一行输出字符串"YouAreWrite!" (不含双引号,注意大小写)。

如果存在一种道路建设的方法满足条件的话,你需要按以下格式输出任意一种方案:

在第二行输出一个整数 $M$,表示道路的个数 接下来 $M$ 行,按修建时间从小到大的顺序输出道路,每行三个整数 $u,v,w$ 表示从 $u$ 到 $v$ 的长度为 $w$ 的道路。

你构造的方案必须满足:$0\leq M\leq K+15$,且 $0\leq w\leq 2^{60}$

样例数据

样例输入

4 6
1 3 2 4 3 4

样例输出

YouAreWrite!
4
1 3 3
1 2 1
2 3 1
3 4 2

子任务

Task1 (7分):$1\leq N\leq 3$。

Task2 (8分):保证在计划表中的数两两不同。

Task3 (9分):保证最多有一个数在计划表中出现超过 $1$ 次。

Task4 (23分):保证计划表中每个数最多出现 $2$ 次。

Task5 (53分):没有限制

对于所有数据,满足 $1\leq N\leq 100$,$1\leq K\leq 10^4$,计划表中的每个数都是 $[1,N]$ 中的整数。