CHAIN - Strange Food Chain
There are 3 kinds of animals A, B and C. A can eat B, B can eat C, C can eat A. It's interesting, isn't it?
Now we have n animals, numbered from 1 to n. Each of them is one of the 3 kinds of animals: A, B, C.
Today Mary tells us k pieces of information about these n animals. Each piece has one of the two forms below:
- 1 x y: It tells us the kind of x and y are the same.
- 2 x y: It tells us x can eat y.
Some of these k pieces are true, some are false. The piece is false if it satisfies one of the 3 conditions below, otherwise it's true.
- X or Y in this piece is larger than n.
- This piece tells us X can eat X.
- This piece conflicts to some true piece before.
The first line contains a single integer t. t blocks follow.
For every block, the first line contains two integers n (1 <= n <= 50000) and k (1 <= k <= 100000). k lines follow, each contains 3 positive integers D (1 <= D <= 2), X, Y, separated by single spaces.
Output t lines, each contains a single integer - the number of false pieces in the corresponding block.
Input: 1 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 Output: 3
The false pieces are the 1st, the 4th and the 5th ones.Warning: large Input/Output data, be careful with certain languages.
I get Accepted in 0.06 in C++ but TLE in Python with the same solution... Is there any optimization that pass the time limit?
Can anyone help me with the solution and explaination?
why 5th query is false ?
nice problem!!: )Last edit: 2019-06-30 13:03:49
this is cool :)Last edit: 2019-01-14 19:11:18
nice problem ):))
Best question on union-find!
why the sentence 5 is false??
Difference between scanf and my fast reading is 0.6s on this problem, so a lot of time is wasted on input reading. Still, with the proper algorithm in C++ you should have no problem with AC. In my case it was 0.7s, where the actual algo took under 0.1s.