Editorial — CC Wing Selection Contest 2026

The input is irrelevant. The required output is fixed and must be printed exactly as given.

This is a direct output problem.

We are given a single string as input, but regardless of what the input contains, we must print the four Terms and Conditions exactly as specified in the statement.

Since the required output is constant, there is no need to process the input.

Just print:

You confirm that you are a IIIT Allahabad Batch 2029 student. You understand that providing false information, copying code may result in removal from the wing. You accept that parties will be scheduled according to the alignment of the stars. You have double checked that you are screen — recording.

Time Complexity: $$$O(1)$$$

Space Complexity: $$$O(1)$$$

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

int main(){
cout<<"1. You confirm that you are a IIIT Allahabad Batch 2029 student.\n";
cout<<"2. You understand that providing false information, copying code may result in removal from the wing.\n";
cout<<"3. You accept that parties will be scheduled according to the alignment of the stars.\n";
cout<<"4. You have double checked that you are screen &mdash; recording.";
}

Try to determine $$$p_1, p_2, p_3, p_4$$$ first using a handful of queries on triples chosen from $$${1,2,3,4}$$$, then use $$$p_1, p_2$$$ as "anchors" to find the rest.

If you query the sum of each triple obtained by leaving out exactly one of $$${1,2,3,4}$$$ at a time, the four query results together encode $$$p_1+p_2+p_3+p_4$$$ redundantly — figure out how to invert this to recover each individual $$$p_i$$$.

We first determine $$$p_1,p_2,p_3,p_4$$$ using $$$4$$$ queries:

• query 1: indices $$$2,3,4 \Rightarrow q_1 = p_2+p_3+p_4$$$
• query 2: indices $$$1,3,4 \Rightarrow q_2 = p_1+p_3+p_4$$$
• query 3: indices $$$1,2,4 \Rightarrow q_3 = p_1+p_2+p_4$$$
• query 4: indices $$$1,2,3 \Rightarrow q_4 = p_1+p_2+p_3$$$

Adding all four queries, every $$$p_i$$$ ($$$1 \le i \le 4$$$) is counted exactly $$$3$$$ times:

So $$$\dfrac{q_1+q_2+q_3+q_4}{3} = p_1+p_2+p_3+p_4$$$.

Now for each $$$i \in {1,2,3,4}$$$, $$$q_i$$$ is exactly the sum of the other three values, i.e. $$$q_i = (p_1+p_2+p_3+p_4) - p_i$$$. Rearranging:

This recovers $$$p_1,p_2,p_3,p_4$$$ using just $$$4$$$ queries.

Once $$$p_1$$$ and $$$p_2$$$ are known, every remaining index $$$i$$$ ($$$5 \le i \le n$$$) can be found with a single query on indices $$$1,2,i$$$:

Total queries: $$$4 + (n-4) = n$$$, well within the interactive limit.

Time Complexity: $$$O(n)$$$ queries per test Space Complexity: $$$O(n)$$$

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

int query(int i,int j,int k){
    int x;
    cout << "? " << i << ' ' << j << ' ' << k << flush << endl;
    cin >> x;
    return x;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> p(n+1);
        int q[5];
        q[1] = query(2,3,4);
        q[2] = query(1,3,4);
        q[3] = query(1,2,4);
        q[4] = query(1,2,3);
        for(int i=1;i<=4;i++) p[i] = (q[1]+q[2]+q[3]+q[4])/3 &mdash; q[i];
        for(int i=5;i<=n;i++) p[i] = query(1,2,i) &mdash; p[1] &mdash; p[2];
        cout << "! ";
        for(int i=1;i<=n;i++) cout << p[i] << ' ';
        cout << flush << endl;
    }
    return 0;
}

Recall the identity that relates addition to bitwise operations: $$$a+b$$$ can be decomposed in terms of $$$a \oplus b$$$ (the "sum without carry") and $$$a & b$$$ (the "carry bits").

Specifically, $$$a+b = (a \oplus b) + 2\cdot(a & b)$$$. You are given $$$a+b$$$ and $$$a&b$$$ directly — can you isolate $$$a \oplus b$$$?

For any two integers $$$a,b$$$, consider adding them bit by bit. At each bit position, $$$a \oplus b$$$ gives the sum of that bit ignoring carry, while $$$a & b$$$ gives exactly the positions where a carry is generated, and that carry gets shifted one position left when added. This gives the identity:

We are given $$$S = a+b$$$ and $$$C = a&b$$$. Rearranging:

Since the input guarantees $$$a,b$$$ are valid non-negative integers consistent with the given $$$S$$$ and $$$C$$$, this value is guaranteed to be non-negative, so no extra validation is needed.

Time Complexity: $$$O(1)$$$ per test Space Complexity: $$$O(1)$$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll sum, andVal;
    cin >> sum >> andVal;
    cout << (sum - 2 * andVal) << '\n';
    return 0;
}

The maximum strength of a connection between two chambers depends only on the maximum GCD achievable between one element from each chamber. You do not need to consider all possible pairs.

A chamber can participate in an edge of weight g if it contains at least one number divisible by g. Use this to group chambers by divisors instead of building all possible edges.

To maximize the total strength, process the groups in descending order of GCD and connect chambers greedily using a Disjoint Set Union (DSU) structure, similar to Kruskal's algorithm for Maximum Spanning Trees.

We want to connect all psychic chambers into a single network with maximum total strength. Since the network must be connected and acyclic, this is a Maximum Spanning Tree problem.

For any two chambers, the best edge between them is the maximum GCD achievable between their elements. We do not need to explicitly build all edges.

Approach:

• For every value v, store all chambers that contain v.
• Iterate over all possible GCD values g from largest to smallest.
• For a fixed g, iterate over all multiples of g and collect all chambers that contain those values.
• Any two such chambers can be connected with an edge of weight at least g.
• Use Disjoint Set Union (DSU) to greedily connect these chambers. Each successful merge adds g to the total answer.

Processing GCDs in descending order ensures that the first time two components are connected, they are connected using their maximum possible GCD. DSU guarantees no cycles and exactly N-1 edges.

This greedy procedure is equivalent to Kruskal's algorithm for Maximum Spanning Tree and produces the optimal result.

Time Complexity: Enumerating multiples follows a harmonic series, giving O(M log M), where M = 2 * 10^5.

Space Complexity: O(N + sum(k_i))

#include <bits/stdc++.h>
using namespace std;
 
// Disjoint Set Union structure for maintaining connected components
struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n,1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]); // path compression
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false; // already connected
        if(sz[a] < sz[b]) swap(a,b); // union by size
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
 
        const int MAXV = 200000;
        vector<vector<int>> pos(MAXV + 1); // pos[x] = list of chambers containing value x
 
        // Read chambers and store positions for each value
        for(int i = 0; i < N; i++){
            int k;
            cin >> k;
            while(k--){
                int x;
                cin >> x;
                pos[x].push_back(i);
            }
        }
 
        DSU dsu(N);
        long long ans = 0;
 
        vector<int> nodes;
        // Process all possible gcd values from largest to smallest
        for(int g = MAXV; g >= 1; g--){
            nodes.clear();
            // Gather all chambers containing multiples of g
            for(int m = g; m <= MAXV; m += g){
                for(int v : pos[m]){
                    nodes.push_back(v);
                }
            }
            if(nodes.empty()) continue;
 
            // Connect all gathered chambers with edges of weight g
            int root = nodes[0];
            for(int i = 1; i < (int)nodes.size(); i++){
                if(dsu.unite(root, nodes[i])){
                    ans += g; // add edge weight to total
                }
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}
 

Fix a split point $$$i$$$ and write out the condition $$$a_1+\cdots+a_i = a_{i+1}+\cdots+a_n$$$ in terms of the prefix sum of $$$b$$$, $$$n$$$, $$$i$$$, and $$$x$$$. You'll get a linear equation in $$$x$$$ — solve for $$$x$$$.

For each fixed $$$i$$$, the equation gives $$$x = \dfrac{2\cdot\text{prefix}_i - \text{total}}{n-2i}$$$. Watch out for two edge cases: the denominator $$$n-2i$$$ can be zero, and $$$x$$$ must be a non-negative integer, not just any real number. Try every $$$i$$$ from $$$1$$$ to $$$n-1$$$ and take the minimum valid $$$x$$$.

Let $$$S_i = b_1+b_2+\cdots+b_i$$$ be the prefix sum of $$$b$$$, and let $$$T = S_n$$$ be the total sum.

For a fixed split index $$$i$$$ ($$$1 \le i \lt n$$$), the condition $$$a_1+\cdots+a_i = a_{i+1}+\cdots+a_n$$$ becomes:

Rearranging:

So for each $$$i$$$ we get a linear equation in $$$x$$$:

• If $$$n-2i = 0$$$: the equation only has a solution when $$$2S_i - T = 0$$$, in which case any $$$x$$$ works, so the minimal choice is $$$x=0$$$.
• If $$$n-2i \ne 0$$$: $$$x = \dfrac{2S_i - T}{n-2i}$$$. This is only a valid candidate if it divides evenly and the resulting $$$x$$$ is a non-negative integer.

We iterate $$$i$$$ from $$$1$$$ to $$$n-1$$$, compute $$$S_i$$$ using a running prefix sum, check divisibility and non-negativity, and take the minimum valid $$$x$$$ over all $$$i$$$. If no $$$i$$$ yields a valid $$$x$$$, output $$$-1$$$.

All quantities ($$$S_i$$$, $$$T$$$, numerator) fit comfortably in a 64-bit integer since $$$n \le 2\cdot10^5$$$ and $$$|b_i|\le 10^9$$$, and the problem guarantees any valid answer is $$$\le 10^{18}$$$, which also fits in a signed 64-bit integer.

Time Complexity: $$$O(n)$$$ per test Space Complexity: $$$O(1)$$$ extra (besides input array)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<ll> b(n+1);
        for(int i=1;i<=n;i++) cin >> b[i];

        vector<ll> pre(n+1,0);
        for(int i=1;i<=n;i++) pre[i] = pre[i-1] + b[i];
        ll total = pre[n];

        bool found = false;
        ll best = LLONG_MAX;

        for(int i=1;i<n;i++){
            ll numerator = 2*pre[i] - total;
            ll denom = (ll)n - 2*i;
            if(denom == 0){
                if(numerator == 0){
                    found = true;
                    best = min(best, 0LL);
                }
            } else {
                if(numerator % denom == 0){
                    ll x = numerator / denom;
                    if(x >= 0){
                        found = true;
                        best = min(best, x);
                    }
                }
            }
        }

        if(found) cout << best << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

We consider a train route (1, v) as an undirected deletable edge (1, v).

Let dist(u) be the shortest path between 1 and u. We add all of the edges (u, v) weighted w where dist(u) + w = dist(v) into a new directed graph.

A deletable edge (1, v) can be deleted only if it isn't in the new graph or the in-degree of v in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of v after you delete an edge (1, v).

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k;
const int maxn = 1e5 + 69;
vector <pair<int, int>> adj[maxn];
int in[maxn];
int d[maxn];
vector <pair<int, int>> e;
vector <pair<pair<int, int> , int>> eg;

void build()
{
    d[1] = 0;
    for (int i=2; i<=n; i++)d[i] = 1e18;
    priority_queue <pair<int, int>> pq;
    pq.push({0, 1});
    while (!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int u = p.second;
        int dist = -p.first;
        if (d[u] != dist) continue;
        for (auto v: adj[u]){
            if (d[v.first] > v.second + dist){
                d[v.first] = v.second + dist;
                pq.push({-d[v.first], v.first});
            }
        }
    }
}

void Solve() 
{
    cin>>n>>m>>k;
    
    for (int i=1; i<=m; i++){
        int u, v, w;
        cin>>u>>v>>w;
        
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        eg.push_back({{u, v}, w});
    }
    
    for (int i=1; i<=k; i++){
        int s, y;
        cin>>s>>y;
        adj[1].push_back({s, y});
        adj[s].push_back({1, y});
        e.push_back({s, y});
    }
    
    build();
    
    int ans = 0;
    for (auto x: eg){
        int u = x.first.first;
        int v = x.first.second;
        int w = x.second;
        if (d[u] == d[v] + w){
            in[u]++;
        } else if (d[v] == d[u] + w){
            in[v]++;
        }
    }
    
    for (auto x: e){
        int s = x.first;
        int y = x.second;
        if (d[s] != y) {
            ans ++;
            continue;
        }
        if (in[s]>0)
        ans++;
        else 
        in[s]++;
    }
    
    cout<<ans;
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

First solve the classic LeetCode Cat and Mouse problem (retrograde/BFS on game states): Cat And Mouse.

Model each game state as a 4-tuple (m_pos, v_pos, mask, turn)

where: — m_pos = Max’s node, — v_pos = Vecna’s node (never 1), — mask = bitmask of rescued children (0..(1<<k)-1), — turn = 0 (Max to move) or 1 (Vecna to move).

This problem is solved exactly like the Cat and Mouse game using retrograde BFS on game states.

The only difference is that when Max visits a node containing a child, we update the mask. Since k ≤ 5, the mask has at most 2^k ≤ 32 possibilities, which is small.

So we just multiply the original Cat & Mouse state space by 32 to track children — everything else stays the same. Time Complexity: $$$ O(n * n * 2^k) $$$ With $$$( n \le 50 , k \le 5 )$$$, this is at most about 160k states, each processed in constant/degree time.

Space Complexity: $ O(n * n * 2^k). for storing outcomes and degrees. Both comfortably fit within limits.

#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;

const int MAXN = 51;
const int MAXK = 32;

int n, m, k;
vector<int> adj[MAXN];
int child_node[MAXN]; // -1 if no child, else 0..k-1
int outcome[MAXN][MAXN][MAXK][2]; // 0: DRAW, 1: MAX, 2: VECNA
int degree[MAXN][MAXN][MAXK][2];

struct State {
    int m_pos, v_pos, mask, turn;
};

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cin >> k;
    for (int i = 1; i <= n; ++i) child_node[i] = -1;
    for (int i = 1; i <= n; ++i) {
        int c; cin >> c;
        if (c != -1) child_node[i] = c;
    }

    queue<State> q;

    // 1. Initialize Degrees and Win/Loss States
    for (int mp = 1; mp <= n; ++mp) {
        for (int vp = 2; vp <= n; ++vp) { // Vecna never at 1
            for (int mask = 0; mask < (1 << k); ++mask) {
                // Max's Turn (0)
                degree[mp][vp][mask][0] = adj[mp].size();
                
                // Vecna's Turn (1)
                for (int next_v : adj[vp]) {
                    if (next_v != 1) degree[mp][vp][mask][1]++;
                }

                // Terminal Condition: Vecna catches Max
                // This happens if Vecna moves to Max, or Max moves to Vecna.
                if (mp == vp) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 2; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 2; q.push({mp, vp, mask, 1}); }
                }
                // Terminal Condition: Max reaches cave with all children
                else if (mp == 1 && mask == (1 << k) - 1) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 1; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 1; q.push({mp, vp, mask, 1}); }
                }
            }
        }
    }

    // 2. Retrograde Propagation
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        int res = outcome[curr.m_pos][curr.v_pos][curr.mask][curr.turn];

        if (curr.turn == 1) { // Current is Vecna, Predecessor was Max
            for (int prev_m : adj[curr.m_pos]) {
                // To reach 'curr.mask' at 'curr.m_pos', Max must have had 'prev_mask'
                // at 'prev_m'. 
                for (int prev_mask = 0; prev_mask < (1 << k); ++prev_mask) {
                    int next_mask = prev_mask;
                    if (child_node[curr.m_pos] != -1) next_mask |= (1 << child_node[curr.m_pos]);
                    
                    if (next_mask == curr.mask) {
                        if (outcome[prev_m][curr.v_pos][prev_mask][0]) continue;

                        if (res == 1) { // Max found a move to win
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 1;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        } else if (--degree[prev_m][curr.v_pos][prev_mask][0] == 0) {
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 2;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        }
                    }
                }
            }
        } else { // Current is Max, Predecessor was Vecna
            for (int prev_v : adj[curr.v_pos]) {
                if (prev_v == 1) continue;
                if (outcome[curr.m_pos][prev_v][curr.mask][1]) continue;

                if (res == 2) { // Vecna found a move to win
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 2;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                } else if (--degree[curr.m_pos][prev_v][curr.mask][1] == 0) {
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 1;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                }
            }
        }
    }

    // 3. Result
    int start_mask = 0;
    if (child_node[2] != -1) start_mask |= (1 << child_node[2]);
    cout << outcome[2][3][start_mask][0] << endl;

    return 0;
}