D - Pigeon Swap Time Limit: 2 sec / Memory Limit:...

Solution Sketch for D – Pigeon Swap

We have $N$ pigeons (numbered $1$ to $N$) and $N$ nests (also numbered $1$ to $N$). Initially, pigeon $i$ sits in nest $i$. There are three types of operations:

1. Type 1 $(1\; a\; b)$:
   Move pigeon $a$ from its current nest to nest $b$.

2. Type 2 $(2\; a\; b)$:
   Swap all pigeons in nest $a$ with all pigeons in nest $b$. These two moves happen simultaneously.

3. Type 3 $(3\; a)$:
   Query which nest pigeon $a$ is currently in.

We must process $Q$ operations in total, possibly up to $3 \times 10^5$, with $N$ up to $10^6$. The main challenge is that a direct or naïve swapping of entire sets (for Type 2) could be very large if done pigeon-by-pigeon. We need an $O(1)$ or at least amortized $O(\log N)$ approach per operation.

Key Idea: “Container” (or “Bucket”) Representation

Instead of literally storing which pigeons are in each nest and swapping them one by one, we use an indirection:

• We maintain containers numbered $1$ to $N$.
• Each container has a “current physical nest label.”
• Each pigeon points to exactly one container (saying: “this pigeon is in container $c$”).

Initially,

• Container $i$ has physical_label[i] = i.
• Pigeon $i$ sits in container $i$.

So pigeon $i$ being “in nest $i$” is encoded as “pigeon $i$ is in container $i$, and container $i$ has physical nest label $i$.”

We also maintain a quick lookup of which container currently corresponds to which physical nest number. Call it container_of_label[]:

• At the start, container_of_label[i] = i for all $i$.

Hence:

• If pigeon $p$ is in container $c$, then the actual nest that pigeon $p$ occupies is physical_label[c].

Operations

1. Type 3 $(3\; a)$ (Query):
   To answer “Which nest is pigeon $a$ in?” we do:

   cpp
   int c = pigeon_container[a];         // container of pigeon a
   int answer = physical_label[c];      // the current physical nest label
   // print `answer`

2. Type 2 $(2\; a\; b)$ (Swap entire nests $a$ and $b$):

   • Find the containers c1 and c2 such that \text{physical_label}[c1] = a,\quad \text{physical_label}[c2] = b.
   • Swap the two containers’ nest labels: \text{swap}\bigl(\text{physical_label}[c1],\ \text{physical_label}[c2]\bigr).
   • Update our reverse lookup so that \text{container_of_label}[\text{physical_label}[c1]] = c1,\quad \text{container_of_label}[\text{physical_label}[c2]] = c2.

   This instantly swaps all pigeons that were “physically in nest $a$” with those “physically in nest $b$,” because we never moved any pigeons around; we only swapped which physical labels (i.e. nest numbers) belong to which container.

3. Type 1 $(1\; a\; b)$ (Move pigeon $a$ to nest $b$):

   • Let old_c = pigeon_container[a].
   • We want to move pigeon $a$ to the nest whose physical label is $b$. Find that container: new_c = container_of_label[b].
   • Remove pigeon $a$ from its old container and place it in new_c. In code, that can simply be:

     cpp
     pigeon_container[a] = new_c;

   • No other pigeons need to move. This is an $O(1)$ action.

Since each of these steps is $O(1)$ (given direct array lookups), we can handle up to $3 \times 10^5$ operations efficiently, and we only store a few arrays of size $N$ (and size $N$ is up to $10^6$, which is still acceptable within 1GB memory limit).

Pseudocode

Below is a condensed form of how one might implement it:

cpp
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 1000000;

// Arrays (1-indexed for convenience if problem is 1-indexed):
// pigeon_container[a] = which container pigeon a currently belongs to
// physical_label[c]   = the physical nest label that container c represents
// container_of_label[L] = which container currently has physical label L

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> pigeon_container(N+1), physical_label(N+1), container_of_label(N+1);

    // Initialize
    for(int i = 1; i <= N; i++){
        pigeon_container[i] = i;     // Pigeon i initially in container i
        physical_label[i]   = i;     // Container i initially has label i
        container_of_label[i]= i;    // Nest label i is held by container i
    }

    while(Q--){
        int op; 
        cin >> op;

        if(op == 1){
            int a,b; 
            cin >> a >> b;
            // move pigeon a to nest b
            int old_c = pigeon_container[a];
            int new_c = container_of_label[b];
            // put pigeon a into container new_c
            pigeon_container[a] = new_c;

        } else if(op == 2){
            int a,b; 
            cin >> a >> b;
            // swap the entire contents of nest a and b
            int c1 = container_of_label[a];
            int c2 = container_of_label[b];
            // swap physical labels
            int tmp = physical_label[c1];
            physical_label[c1] = physical_label[c2];
            physical_label[c2] = tmp;
            // update container_of_label
            container_of_label[ physical_label[c1] ] = c1;
            container_of_label[ physical_label[c2] ] = c2;

        } else {
            // query
            int a; 
            cin >> a;
            int c = pigeon_container[a];
            int ans = physical_label[c];
            cout << ans << "\n";
        }
    }
    return 0;
}

All operations work in $O(1)$ time. For large $N,Q$, this approach stays efficient and fits memory constraints.

Solution Sketch for E – Flip Edge

We have a directed graph of $N$ vertices and $M$ edges. You start at vertex $1$. You want to reach vertex $N$. Two types of operations are possible:

1. Move along an existing directed edge at a cost of $1$.

   • If you are at vertex $v$, you can move to $u$ if there is an edge $v \to u$.

2. Reverse all edges in the entire graph at a cost of $X$.

   • Immediately after reversing, every edge $v \to u$ becomes $u \to v$.

We want the minimum total cost to go from vertex $1$ to vertex $N$. Note that we can do the reversal any number of times, each time paying cost $X$.

Standard Trick: “State” = (Vertex, Orientation)

Since edges can be either in the original orientation or in the reversed orientation, define the orientation bit as $0$ or $1$:

• Orientation $0$ means “the graph is in its original direction.”
• Orientation $1$ means “the graph has been reversed from the original.”

A flip operation toggles between orientation $0$ and orientation $1$.

Hence we consider an expanded graph of size $2N$ “states”:

• State $(v, 0)$: You are at vertex $v$ with the graph in orientation $0$.
• State $(v, 1)$: You are at vertex $v$ with the graph in orientation $1$.

Transitions

1. Move along a directed edge (cost = 1):

   • If orientation = 0, from $(v, 0)$ you can move to $(u, 0)$ if there is an original edge $v \to u$.
   • If orientation = 1, from $(v, 1)$ you can move to $(u, 1)$ if there is an original edge $u \to v$ (because in orientation 1, edges are reversed).

2. Flip orientation (cost = $X$):

   • From $(v, 0)$ you can go to $(v, 1)$ at cost $X$.
   • From $(v, 1)$ you can go to $(v, 0)$ at cost $X$.

We want the shortest path from $(1, 0)$ to $(N, 0)$ or $(N, 1)$. Once you reach vertex $N$ in either orientation, you are done (the problem states we only care about arriving at $N$).

Dijkstra’s Algorithm on 2-Layer Graph

Since each edge has cost either $1$ or $X$, and $X$ can be as large as $10^9$, we use a normal Dijkstra (with a priority queue), not a 0–1 BFS. The graph has:

• Vertices: $(v, 0)$ and $(v, 1)$ for $v = 1,2,\dots, N$. So $2N$ states in total.
• Edges:
  1. For each original directed edge $(v \to u)$, we add:
     • $(v,0) \to (u,0)$ with cost 1.
     • $(u,1) \to (v,1)$ with cost 1. (Because in orientation 1, an edge $v \to u$ is reversed to $u \to v$.)
  2. For each vertex $v$:
     • $(v,0) \leftrightarrow (v,1)$ with cost $X$.

The number of edges is about $2M$ for the “move” edges (forward and reversed) plus $2N$ for the “flip” edges, which is acceptable for $M \le 2\times 10^5$ and $N \le 2\times 10^5$.

Then we run Dijkstra from $(1, 0)$. Let dist[v][orient] = minimum cost to reach state $(v, orient)$. Initialize dist[1][0] = 0, all others ∞. Use a priority queue (min-heap).

At the end, the answer is

Implementation Outline

1. Read $N, M, X$.
2. Build two adjacency lists:
   • adjF[v] for forward edges (from $v$ to its neighbors).
   • adjR[v] for reversed edges (if the original has $v \to u$, then in adjR[u] we store $v$).
3. Use a structure like:

   cpp
   // We'll store edges of the form: (to, cost).
   vector<vector<pair<int, long long>>> graph(2*N + 1);

   But more commonly, we just keep two separate adjacency lists for orientation=0 and orientation=1 logic, then handle flipping in Dijkstra code.
4. Run Dijkstra on the 2*N state-graph:
   • Distances array: dist[v][0] and dist[v][1].
   • Priority queue states: (current_cost, vertex, orientation).
   • Relax edges according to the rules above.
5. Print min(dist[N][0], dist[N][1]).

Since $N, M \le 2\times 10^5$, a standard Dijkstra with $O((N + M)\log N)$ (roughly) is usually efficient enough in 2 seconds.

Edge Cases

• $X$ can be huge ($\le 10^9$) or smaller than 1.
• Possibly it is faster never to flip (if $X$ is huge) or to flip once or multiple times. The algorithm automatically finds the best approach.
• The answer might exceed 32-bit integer range, so store distances in a 64-bit type (long long in C++ or long in Java/Python).

Final Remarks

• D – Pigeon Swap: Use containers + swapping labels in $O(1)$.
• E – Flip Edge: Model as a 2-layer (orientation-0, orientation-1) graph and run Dijkstra.

These methods handle the given constraints efficiently and are standard approaches for such “swap-all” or “flip-all” style problems.