All Tracks Problem

Xor thing
Tag(s):

Graph Theory, Hard

Problem
Editorial
Analytics

Given a graph with vertices divided into $$N$$ groups, each containing $$2^M$$ vertices that are numbered from $$0$$ inside the group.
Initially there is no edge. There are $$Q$$ queries. Each query will be of one of the following 3 types:
$$1 \space i \space j \; p$$: For every vertex numbered $$x$$ from $$0$$ to $$2^m-1$$ add an edge between vertex $$x$$ from group $$i$$ and vertex $$x \oplus p$$ from group $$j$$.
$$2 \; i \; x$$: Find the size of component containing vertex $$x$$ in group $$i$$.
$$3$$: Count the total number of connected components.

Input Format:
First line consists of three space separated integers denoting $$N$$, $$M$$ and $$Q$$.
$$Q$$ lines follow, each containing one of the given $$3$$ types of queries.

Output Format:
For every query of type $$2$$ and $$3$$ print the required answer in a new line.

Constraints:
$$1 \le N \le 10^5$$
$$1 \le M \le 40$$
$$1 \le Q \le 4 \times 10^5$$
$$0 \le p, x \le 2^M-1$$
$$1 \le i, j \le N$$

SAMPLE INPUT
3 1 3
1 1 2 1
3
2 2 0
SAMPLE OUTPUT
4
2
Explanation

The first query connects following vertices:
Vertex $$0$$ of group $$1$$ to vertex $$1$$ of group $$2$$.
Vertex $$1$$ of group $$1$$ to vertex $$0$$ of group $$2$$.

So connected components is $$4$$.
Size of component containing vertex $$0$$ of group $$2$$ is $$2$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications