WC '18 Contest 4 S1 - World of StarCraft - DMOJ: Modern Online Judge

WC '18 Contest 4 S1 - World of StarCraft

Points: 10 (partial)

Time limit: 1.4s

Memory limit: 128M

Author:

Problem type

Woburn Challenge 2018-19 Round 4 - Senior Division

Billy, the king of video games, is (among other things) a top professional StarCraft II player. In light of his recent success as the only human to defeat the fearsome AlphaStar AI, he has received exclusive access to play the upcoming installment in the series, World of StarCraft. In a natural progression for the series, this is a massively multiplayer online role-playing game.

World of StarCraft features $N$ $N$ $(2 \le N \le 100\,000)$ $(2 \leq N \leq 100 000)$ planets, numbered from $1$ $1$ to $N$ $N$ . Each planet is under the control of one of three races (Protoss, Terran, or Zerg), with the character $R_i$ $R_{i}$ representing planet $i$ $i$ 's race (either P for Protoss, T for Terran, or Z for Zerg).

There are $M$ $M$ $(0 \le M \le 100\,000)$ $(0 \leq M \leq 100 000)$ space routes running amongst the planets, with the $i$ $i$ -th space route allowing one to travel in either direction between planets $A_i$ $A_{i}$ and $B_i$ $B_{i}$ $(1 \le A_i, B_i \le N, A_i \ne B_i)$ $(1 \leq A_{i}, B_{i} \leq N, A_{i} \neq B_{i})$ . There may be multiple space routes connecting a single pair of planets.

Despite its secretive and unreleased development status, World of StarCraft somehow already has an enormous player-base. Billy himself has $K$ $K$ $(1 \le K \le 100\,000)$ $(1 \leq K \leq 100 000)$ friends in the game. His $i$ $i$ -th friend is currently on planet $X_i$ $X_{i}$ , and would like to reach a different planet $Y_i$ $Y_{i}$ to complete an objective $(1 \le X_i, Y_i \le N; X_i \ne Y_i)$ $(1 \leq X_{i}, Y_{i} \leq N; X_{i} \neq Y_{i})$ .

When a player is on planet $i$ $i$ , they may travel along a space route to another planet $j$ $j$ , assuming that a space route exists which connects planets $i$ $i$ and $j$ $j$ . However, due to open hostilities amongst the three races, it's only safe to do so if both planets are under the control of the same race (in other words, if $R_i = R_j$ $R_{i} = R_{j}$ ).

Billy would love to help all of his friends complete their objectives, but not without putting their in-game lives at risk! Help him determine how many friends $i$ $i$ he has such that it's possible to safely travel through a sequence of planets beginning at planet $X_i$ $X_{i}$ and ending at planet $Y_i$ $Y_{i}$ .

Subtasks

In test cases worth $8/14$ $8 / 14$ of the points, $N \le 1\,000$ $N \leq 1 000$ , $M \le 1\,000$ $M \leq 1 000$ , and $K \le 1\,000$ $K \leq 1 000$ .

Input Specification

The first line of input consists of three space-separated integers, $N$ $N$ , $M$ $M$ , and $K$ $K$ .
The next line consists of characters, $R_{1 \dots N}$ $R_{1 \dots N}$ .
$M$ $M$ lines follow, the $i$ $i$ -th of which consists of two space-separated integers, $A_i$ $A_{i}$ and $B_i$ $B_{i}$ , for $i = 1 \dots M$ $i = 1 \dots M$ .
$K$ $K$ lines follow, the $i$ $i$ -th of which consists of two space-separated integers, $X_i$ $X_{i}$ and $Y_i$ $Y_{i}$ , for $i = 1 \dots K$ $i = 1 \dots K$ .

Output Specification

Output a single integer, the number of friends who can safely complete their objectives.

Sample Input

Copy

Sample Output

Copy

Sample Explanation

Billy's first friend can safely travel directly from planet $6$ $6$ to planet $4$ $4$ to complete their objective.

Billy's second friend may never safely reach planet $3$ $3$ .

Billy's third friend can safely travel through the sequence of planets $1 \to 4 \to 6 \to 5$ $1 \to 4 \to 6 \to 5$ .

Comments

There are no comments at the moment.