Hyper Disjoint Set | MatCom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

H - Hyper Disjoint Set

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

You are asked to maintain a dynamic undirected graph under a sequence of operations.

Initially, the graph consists of a single node (labeled $1$) and no edges. Then, you must process a sequence of operations of the following types:
* **Add edge**
   `LINK u v`
	 Add an edge between nodes $u$ and $v$. It is guaranteed that both nodes exist at this moment.

* **Duplicate graph**
  `DUP`
  If the current graph contains $n$ nodes, extend it to contain $2n$ nodes as follows:
     * For every edge $(u,v)$ with $1 \leq u,v \leq n$ in the current graph, add edges $(u,v)$ and $(u+n, v+n)$ in the new graph.
     * No additional edges are added between the two halves.

*  **Duplicate and link graph**
  `DUPLINK`
	If the current graph contains $n$ nodes, extend it to contain $2n$ nodes as follows:
     * For every edge $(u,v)$ with $1 \leq u,v \leq n$ in the current graph, add edges $(u,v)$ and $(u+n, v+n)$ in the new graph.
     * Additionally, for every $1 \leq u \leq n$, add an edge $(u, u+n)$ between the original node and its copy.

* **Connectivity query**
  `ASK u v`
	Determine whether nodes $u$ and $v$ are in the same connected component.

Input

Output

Sample test(s)

Input

2 9 DUP DUP LINK 1 2 LINK 1 3 ASK 1 3 ASK 2 3 ASK 1 4 LINK 3 4 ASK 1 4 11 DUPLINK DUP LINK 2 3 ASK 1 3 DUP ASK 8 7 ASK 2 8 LINK 4 6 ASK 2 8 LINK 6 6 ASK 5 5

--- Showing first 30 lines (click "Copy" to get full content) ---

Output

YES YES NO YES YES YES NO YES YES

--- Showing first 30 lines (click "Copy" to get full content) ---

Matcom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

H - Hyper Disjoint Set

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)