http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1341. 生日蜡烛(沈添笑)
时间限制:2.0s   内存限制:256.0MB  
总提交次数:6   AC次数:3   平均分:50.00
将本题分享到:
   
 
【问题描述】

  小A的生日到了!生日派对上,大家送上了一份精心准备的大礼:生日蛋糕!蛋糕上五颜六色的蜡烛闪闪发光、随风摇曳。小A很喜欢这个漂亮的蛋糕,然而,在吹蜡烛许愿的时候,他却犯难了:烛火怎么也吹不灭!原来,这是大家要考考小A。这份特制的蛋糕上共有n根蜡烛,编号为1~n,相应的,有n个开关,第i根蜡烛由第i个开关控制。此外,第i根蜡烛还可能由至多一个其他的开关j控制,当i=1时,j可以是2~n中的任意一个数,当i>1时,j<i。按下一个开关,它所控制的蜡烛的状态就会发生改变:由亮变暗或由暗变亮。小A知道每根蜡烛此时是亮是暗,以及它由哪些开关控制,他希望尽量少地按开关,使所有的蜡烛熄灭。不过,参加聚会的m个同学并不打算就这样放过可怜的小A,他们会依次改变某个蜡烛的状态以及控制它的开关,并询问小A此时最少要按多少次开关。快来帮帮小A吧,他会亲手切下第一块生日蛋糕送给你的!

【输入格式】

  第一行为一个正整数n,表示蜡烛和开关的个数。
  接下来n行,第i行描述第i根蜡烛。每行包含两个整数,第一个数ai为0(暗)或1(亮),代表蜡烛的状态,第二个数bi为控制第i根蜡烛的另一个开关,bi=0时表示第i根蜡烛只由第i个开关控制。
  接下来一行为一个正整数m,表示参加派对的人数。
  接下来m行,每行包含三个整数u、v、w,代表第u根蜡烛的状态变为v,控制它的另一个开关变为w。

【输出格式】

  输出应有m行,第i行一个整数timei,表示经过前i次修改后,此时最少需按多少次开关,才能使所有蜡烛熄灭。若是无论如何都不能使所有蜡烛熄灭,输出-1。

【样例输入】

  4
  1 3
  1 0
  0 1
  1 2
  3
  1 0 3
  4 1 3
  3 0 2

【样例输出】

  1
  2
  3

【数据范围】

  10%的数据满足:n、m≤10
  20%的数据满足:n、m≤1000
  另有20%的数据满足:控制蜡烛的开关不会更改,即w=bu,且bi=(i+n-2)%n+1
  另有30%的数据满足:控制蜡烛的开关不会更改
  100%的数据满足:n、m≤100000