oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

truthandlies Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

After showing you his awesome, eye catching dance, Guan has suddenly ended up in another room in the dance arena.

In this room are p people, of two kinds, Liars and Truth Tellers. Liars always lie and Truth Tellers always tell the truth.

Each of the people in this room will make multiple statements about the other people in this room and there will be n statements in total.

Each person will either state that another person is telling the truth or lying (Each person knows every other person's identities and A liar will state that another person who tells the truth is lying) or he(/she) will state that the other person is either of the same or of a different type.

After hearing so many statements, Guan is confused and has hurt himself in his confusion :-(

Guan would like you to help him find out which people are definitely liars or truth tellers so that he can know who to trust.

An Illustration

XKCD 246

Another Illustration

Input

The first line of the input will be the number of people, p followed by the number of statements, n

The rest of the lines of input will consist of a single integer, i indicating the id of the person who said the statement, followed by another integer j indicating the id of the person he(/she) is referring to and finally, a string saying either TRUTH, LIAR, SAME or DIFFERENT to indicate whether he(/she) says the other person is telling the truth, lies or is of the same type as herself or of a different type to herself.

It is guaranteed that there will be no contradictory or repeated statements and people may comment about themselves

Note: A person can comment on him(/her)self

Output

A single of characters which indicate 'T' if a person is definitely a truth teller, 'F' if he(/she) is definitely a liar and '?' otherwise

Subtasks

Subtask 1 (11%) p,n<=20

Subtask 2 (18%) p,n<=1000

Subtask 3 (9%) p,n<=1000000, there will be no SAME or DIFFERENT statements

Subtask 4 (17%) p,n<=1000000, there will be no TRUTH or LIAR statements

Subtask 5 (45%) p,n<=1000000, no further restrictions

Subtask 6 (0%) will be the sample testcases

Sample Testcase 1

Input

5 5
1 2 TRUTH
1 3 LIAR
1 4 DIFFERENT
4 1 SAME
1 5 TRUTH
Output
TTFFT

Explanation

1 always tells the truth, so he will say 2 is telling the truth, 3 is lying, 4 is different and 5 is telling the truth. 4 is lying, so he will say 1 is the same. No other combination of 5 people results in the same pairs of statements

Sample Testcase 2

Input

3 2
1 2 SAME
2 1 SAME
Output
TT?

Explanation

Either TTF or TTT satisfy the above statements, so, we do not know whether the 3rd person is telling the truth or lying

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
111102s64MBMinimum
218102s64MBMinimum
39102s64MBMinimum
417102s64MBMinimum
545102s64MBMinimum
6022s64MBAverage

Judge Compile Command

g++-8 ans.cpp -o truthandlies -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.