Chef and New Year Present
All submissions for this problem are available.Chef's friend Leo told Chef that he would give him a present on the occasion of New Year. Although Chef was very happy to know that, Leo imposed a condition on which gift to give. There were two choices- either a book on algorithms or a video game. To decide the gift, Leo gave Chef the following problem: A graph is given consisting of $n$ nodes where each node has a value. An array $ar$ is given where the value of $i$th node of the graph is given by $ar_i$, $1 \leq i \leq n$. The graph has $e$ edges. Each edge joins two vertices, $x$ and $y$, $1 \leq x,y \leq n$. Leo gives chef $Q$ queries to answer. There are 2 types of queries: - $1$ $p$ $q$- Update the value of the $p$th node to $q$ - $2$ $p$ $q$- Find the number of nodes that are reachable from the $p$-th node(including the $p$th node) and has value $q$. Output only for the second type of query. If Chef answers all queries correctly, he would get his desired gift(obviously, it is the book on algorithms) but he is unable to solve the problem and needs your help. Can you help him? ###Input: - The first line contains 3 space separated integers- $n$,$e$ and $Q$. - Next line contains $n$ space-separated integers- $ar_1,ar_2,...,ar_n$ - Each of the next $e$ lines contains 2 space separated integers, $x$ and $y$. - Each of the next $Q$ lines contains 3 space separated integers- $t$, $p$ and $q$, where $t$ states the type of query. ###Output: Print an integer in a new line for each query of second type. ###Original Constraints - $1 \leq n,e,Q \leq10^5$ - $1 \leq ar_i \leq100$ - $1 \leq x,y \leq n$ - $1 \leq t \leq 2$ - $1 \leq p \leq n$ - $1 \leq q \leq 100$ ###Subtasks - 30 points : $1 \leq n,e,Q \leq1000$ - 70 points : Original Constraints ###Sample Input: 7 4 3 2 3 2 5 3 1 1 1 2 1 3 5 6 6 7 2 2 2 1 7 3 2 5 3 ###Sample Output: 2 2 ###Explanation: In 1st query, the nodes reachable from 2nd node are 1, 2 and 3. Nodes 1 and 3 have value 2. So, the answer is 2. In 2nd query, the value of the 7th node is changed to 3. In 3rd query, the nodes reachable from 5th node are 5, 6 and 7. Nodes 5 and 7 have value 3. So, the answer is 2.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.