AKBAR - Akbar , The great


 

All of us are familiar with the reign of the great mughal ruler , Akbar. He was always concerned with the prosperity and safety of the people . Therefore to safeguard his kingdom (which consisted of N cities) he wanted to place secret soldiers all over his kingdom so as to protect the people . But since his kingdom is very large therefore he wanted to place as minimum of them as possible because the salary of these undercover soldiers was very high ,ie, in such a way that every city is protected by only one soldier .
 As for these soldiers , they have varible strength .
The strength of a particular soldier is defined as the number of cities he can safeguard from a particular city along with that city. 
Also the kingdom is connected with a network of secret two way roads for faster access only accessible to these soldiers. The length of any road on this network between any two cities is 1 kms .There are R such roads in the kingdom. 
He had given this task to birbal to place the soldiers . Birbal didn't wanted to be a fool in front of the king , therefore took the job and placed M soldiers all over the kingdom but he was not very good at mathematics . But since he is very intelligent he somehow places the guards all over the kingdom and now turns to you (who is a genius mathematician ;) ) to check whether his placements are good or not.
Your task is to check if all the placements of the soldiers are optimum or not.
INPUT
The input consists of t test cases . Each test case then consists of 3 parts.The first line consists of N and R and M.
the next R lines consists of two numbers a and b denoting the two cities between which a road exists .
the next M lines consists of 2 numbers k and strength denoting the city number and the strength of that particular soldier respectively .
=> strength 0 means it will only guard the city on which it is present .
=> assume every city is accesible from every other city .
CONSTRAINTS
t <= 10;
1 <= N <= 10^6;
N-1 <= R <= min(10^9 , (N*(N-1))/2));
1 <= k <= N;
0 <= strength <= 10^6
OUTPUT
print "Yes" if the soldiers are placed optimumly else print "No". (quotes are for clearity)
SAMPLE INPUT
3 2 2
1 2
2 3
1 2
2 0
4 5 2
1 4
1 2
1 3
4 2
3 4
2 1
3 0
SAMPLE OUTPUT
No
Yes
WARNING ==> Large input . Be careful with certain languages. Use scanf() for c/c++ ;

All of us are familiar with the reign of the great mughal ruler , Akbar. He was always concerned with the prosperity and safety of the people . Therefore to safeguard his kingdom (which consisted of N cities) he wanted to place secret soldiers all over his kingdom so as to protect the people . But since his kingdom is very large therefore he wanted to place them in such a way that every city is protected by one and only one soldier.According to Akbar , this is the optimum placement.

 As for these soldiers they can protect multiple cities according to their strengths.

The strength of a particular soldier is defined as the maximum distance upto which a guard can protect a city from its base city(base city is the city assigned to the guard). If there are 3 cities C1, C2 and C3 such that C1 C2 and C2 C3 are connected respectively, if a soldier with strength 1 is placed at C2 then all the cities C1, C2 and C3 are protected by that soldier.

Also the kingdom is connected with a network of secret two way roads for faster access only accessible to these soldiers. The length of any road on this network between any two cities is 1 kms .There are R such roads in the kingdom. 

He had given this task to birbal to place the soldiers . Birbal didn't wanted to be a fool in front of the king , therefore took the job and placed M soldiers all over the kingdom but he was not very good at mathematics . But since he is very intelligent he somehow places the guards all over the kingdom and now turns to you (who is a genius mathematician ;) ) to check whether his placements are good or not.

 

Your task is to check if the placements of the soldiers are optimum or not.

 

INPUT

 

The input consists of T test cases . Each test case then consists of 3 parts.The first line consists of N, R and M.

the next R lines consists of two numbers A and B denoting the two cities between which a road exists .

the next M lines consists of 2 numbers, city number K and strength S of that particular soldier.

 

=> strength 0 means it will only guard the city on which it is present .

=> assume every city is accesible from every other city .

 

CONSTRAINTS

 

T <= 10;

1 <= N <= 10^6;

-1 <= R <= min( 10^7 , ( * (- 1) ) / 2) );

1 <= K <= N;

0 <= S <= 10^6

 

OUTPUT

 

print "Yes" if the soldiers are placed optimumly else print "No". (quotes are for clarity)

 

SAMPLE INPUT

 

2

3 2 2

1 2

2 3

1 2

2 0

4 5 2

1 4

1 2

1 3

4 2

3 4

2 1

3 0

 

SAMPLE OUTPUT

 

No

Yes

 

WARNING ==> Large input.

 


hide comments
rushi2001: 2021-04-19 22:01:48

Got AC in 5th Attempt
Special Thanks to
@code_aim
for TC
1
6 6 1
1 2
1 3
2 4
3 5
4 6
5 6
1 3
ans - Yes

sanchit2812: 2021-04-15 13:37:13

@als1510 You have to assign only one soldier to a city, in the first testcase: 2 would have 2 soldiers. so ans : NO

als1510: 2021-04-10 18:14:08

I can't be able to understand the first test case . if first city's soldier has strength 2 then he can also protect the remaining two nodes. So why ita answer is "NO"

abhinandan824: 2021-04-01 09:20:51

Please can somebody explain the solution. I am stuck now and can't find any method. I have used dfs for finding k nearest neighbor and maintaining a vis array which I am incrementing and after doing dfs for all soldiers nodes. and after that checking if at any node vis[i] is greater than 1 or equal to 0 because a node can't be unprotected or protected by more than 1 soldier

sayskar: 2021-03-22 08:58:34

dfs works !! just need to keep track of parent

vivek_prime: 2021-03-03 12:32:01

i think they are accepting wrong solutions
for this case
ans must be "NO" for this test case:
1
4 4 2
1 2
2 4
4 3
1 3
1 0
3 2

city 1 is protected by two soldiers

my sol is giving no but a sol which is accepted there gives yes
Admin please check

pal550: 2021-02-21 18:58:36

Test Cases are very Weak. Many accepted Solutions are not holistically correct.
Test Case:
3
4 3 2
1 2
2 3
2 4
1 2
3 1
4 4 1
1 2
2 3
3 4
4 1
1 4
4 3 2
1 2
1 3
3 4
1 1
4 1
Correct Output:
No
Yes
No
Many accepted solutions fail here.

csdeshpande19: 2021-02-17 19:32:39

AC!
Think about BFS from each soldier (multi-source BFS)

ashutosh_coder: 2021-01-22 15:52:29

*one and only one*
important line
accepted in one go

Last edit: 2021-01-22 15:53:10
izaj: 2020-12-03 18:20:31

Weak Online Judge
My solution got accepted, but there is some logical error in my code.
Consider the graph below
1 2
2 3
2 4
And, soldiers are placed at
1 2
3 1
It should print NO as 2 is covered by 2 soldiers. But my code printed Yes and it gets passed.

Last edit: 2020-12-03 18:22:06

Added by:Prayank Mathur
Date:2014-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own