| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Game Leader
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 244 Accepted Submission(s): 87
Problem Description
Recently Tom is playing an interesting game. The game contains a social network, so players can make friends with each other. The friend relation is symmetric, which means if A is a friend of B, B is also a friend of A.
Players¡¯ ratings are distinct from each other, which means there are no two players sharing a same rating. Each player owns a ranklist containing all his friends¡¯ rating (including himself) and there is one leader who has the highest rating in each player¡¯s ranklist.
Tom has N friends. During the communications with these friends, he knows some pairs of friends are also friends. But he doesn¡¯t know all the such pairs. In other words, some friends maybe are friends but Tom doesn¡¯t know it.
One day, Tom noticed that the system started showing the number of leaders for every friend.
E.g. the system may says Peter is leader on 3 players¡¯ ranklist.
Now Tom can see the number of leaders for every friend. He would like to know the least number of strangers¡¯ ranklist leader are his friends.
Players¡¯ ratings are distinct from each other, which means there are no two players sharing a same rating. Each player owns a ranklist containing all his friends¡¯ rating (including himself) and there is one leader who has the highest rating in each player¡¯s ranklist.
Tom has N friends. During the communications with these friends, he knows some pairs of friends are also friends. But he doesn¡¯t know all the such pairs. In other words, some friends maybe are friends but Tom doesn¡¯t know it.
One day, Tom noticed that the system started showing the number of leaders for every friend.
E.g. the system may says Peter is leader on 3 players¡¯ ranklist.
Now Tom can see the number of leaders for every friend. He would like to know the least number of strangers¡¯ ranklist leader are his friends.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consists of 3 integers, N, M and R representing the number of people on Tom¡¯s ranklist(including Tom), the number of friendships Tom knows and the rank of Tom in his ranklist(1-indexed). The next line consists of N integers, the $i^{th}$ integer $C_i$ represents the number of leaders for the friend on rank i. The following M lines each consists of 2 integers $X_i$ , $Y_i$ , means that the friend on rank $X_i$ is a friend of friend on rank $Y_i$.
Output
For each test case, output one line containing ¡°Case #x: y¡±, where x is the test case number (starting from 1) and y is the least number of ranklists that not owned by Tom¡¯s friend but the leader is Tom¡¯s friend.
$\bullet 1 ¡Ü T ¡Ü 100.$
$\bullet 1 ¡Ü N, M ¡Ü 10^5.$
$\bullet 1 ¡Ü X_i ¡Ü N.$
$\bullet 1 ¡Ü Y_i ¡Ü N.$
$\bullet 1 ¡Ü R ¡Ü N.$
$\bullet R \neq X_i .$
$\bullet R \neq Y_i .$
$\bullet X_i \neq Y_i .$
$\bullet 0 ¡Ü C_i ¡Ü 10^9.$
$\bullet$ It¡¯s guaranteed that the data is valid.
limits
$\bullet 1 ¡Ü T ¡Ü 100.$
$\bullet 1 ¡Ü N, M ¡Ü 10^5.$
$\bullet 1 ¡Ü X_i ¡Ü N.$
$\bullet 1 ¡Ü Y_i ¡Ü N.$
$\bullet 1 ¡Ü R ¡Ü N.$
$\bullet R \neq X_i .$
$\bullet R \neq Y_i .$
$\bullet X_i \neq Y_i .$
$\bullet 0 ¡Ü C_i ¡Ü 10^9.$
$\bullet$ It¡¯s guaranteed that the data is valid.
Sample Input
2 4 0 3 1 0 0 2 4 1 4 1 0 2 0 1 3
Sample Output
Case #1: 2 Case #2: 2
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-05-01 06:48:07, Gzip enabled |
Administration |