若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1570: War

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,076

题目描述

A war is being fought between two countries, A and B. As a loyal citizen of C, you decide to help your country by secretly attending the peace talks between A and B. There are n other people at the talks, but you do not know which person belongs to which country. You can see people talking to each other, and by observing their behavior during occasional one-to-one conversations you can guess if they are friends or enemies.

Your country needs to know whether certain pairs of people are from the same country, or whether they are enemies. You can expect to receive such questions from your government during the peace talks, and will have to give replies on the basis of your observations so far.

Now, more formally, consider a black box with the following operations:

setFriends(x,y) shows that x and y are from the same country

setEnemies(x,y) shows that x and y are from different countries

areFriends(x,y) returns true if you are sure that x and y are friends

areEnemies(x,y) returns true if you are sure that x and y are enemies

The first two operations should signal an error if they contradict your former knowledge. The two relations “friends'' (denoted by ) and “enemies'' (denoted by *) have the following properties:

is an equivalence relation: i.e.,
If x~ y and y ~ z, then x ~ z (The friends of my friends are my friends as well.)
If x ~ y, then y~ x (Friendship is mutual.)
x ~ x (Everyone is a friend of himself.)
*
is symmetric and irreflexive:
If x*y then y*x (Hatred is mutual.)
Not x*x (Nobody is an enemy of himself.)
If x*y and y*z then x ~ z (A common enemy makes two people friends.)
If x ~ y and y*z then x*z (An enemy of a friend is an enemy.)
Operations setFriends(x,y) and setEnemies(x,y) must preserve these properties.

输入

The first line contains a single integer, n, the number of people. Each subsequent line contains a triple of integers, c x y, where c is the code of the operation,

c = 1, setFriends
c = 2, setEnemies
c = 3, areFriends
c = 4, areEnemies

and x and y are its parameters, integers in the range [0, n) identifying two different people. The last line contains 0 0 0.
All integers in the input file are separated by at least one space or line break. There are at most 10,000 people, but the number of operations is unconstrained.

输出

For every areFriends and areEnemies operation write “0'' (meaning no) or “1'' (meaning yes) to the output. For every setFriends or setEnemies operation which conflicts with previous knowledge, output a “-1'' to the output; such an operation should produce no other effect and execution should continue. A successful setFriends or setEnemies gives no output.

All integers in the output file must be separated by one line break

样例输入

10
1 0 1
1 1 2
2 0 5
3 0 2
3 8 9
4 1 5
4 1 2
4 8 9
1 8 9
1 5 2
3 5 2
0 0 0


样例输出

1
0
1
0
0
-1
0


参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 Skip 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist