National Olympiad in Informatics, China, 2001
Day 1, Problem 1 - Food Chain
The animal kingdom contains three species of animals A, B, and C. The food chain of these animals form an interesting loop shape, where A eats B, B eats C, and C eats A.
There are N animals, each uniquely labeled with a number from 1 to N. Each animal is either of species A, B, or C, but we do not ultimately know which animal is which species.
An individual uses two methods to describe the relationship between the animals in their food chain:
- The first method is using the format "
1 X Y", indicating that X and Y belong to the same species.
- The second method is using the format "
2 X Y", indicating that X eats Y.
Regarding these N animals, this individual makes K statements using the two above formats. Some of these K statements will be true, and others will be lies. When a statement fulfills one of the following conditions, the statement is a lie. Otherwise the statement is true.
- If the current statement conflicts with an already stated true statement, then the current statement is a lie.
- If the current statement has X or Y greater than N, then the current statement is a lie.
- If the current statement indicates that X eats X, then the statement is a lie.
Your task is, given a number N (1 ≤ N ≤ 50 000) and K statements (0 ≤ K ≤ 100 000), determine the total number of false statements.
The first line of input contains two integers N and K, separated by a space.
The next K lines each contain three integers D, X, and Y, separated by spaces.
D = 1 indicates that X and Y are the same species. D = 2 indicates that X eats Y.
The output should consist of a single integer - the number of false statements.
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
For the 7 statements:
1 101 1is a lie.
2 1 2is true.
2 2 3is true.
2 3 3is a lie.
1 1 3is a lie.
2 3 1is true.
1 5 5is true.
Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 08, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3