If we have a square $$$s$$$ and another square $$$S$$$ that completely covers $$$s$$$, then the intersection of $$$s$$$ and $$$S$$$ is a valid square.

Recall that we can pick any valid square, so long as the coordinates for both axes are in the range $$$[-10^9, 10^9]$$$.

Note that all coordinates for our squares are in the range $$$[-10^9, 10^9]$$$. Also, consider that we are allowed to print any square that satisfies the condition in the problem statement.

Consider Hint 1: if another square completely covers one square, then their intersection remains a square. Thus, the easiest construction is for our square $$$S$$$ to cover all the input squares completely.

Because of this, we can print a square with its lower-left corner at $$$(-10^9, -10^9)$$$ and its upper-right corner at $$$(10^9, 10^9)$$$.

inf = 10**9
print(-inf, -inf, inf, inf)

How do you find the optimal path? Think greedy.

The $$$\text{MEX}$$$ is the smallest number not present in the path. You already have the optimal path. Recall that all values from $$$0$$$ to $$$n + 1$$$ are present.

The key observation is that you should always take the smallest number in each layer: if you were to take another number in the layer, the evaluation score must be at most the smallest number in that layer.

To show that this is true, suppose we chose the path containing the minimum value in each layer. Let's denote the $$$\text{MEX}$$$ as $$$m$$$. For each layer, let's denote the minimum value $$$a_i$$$ where $$$i$$$ is the layer. If $$$a_i \lt m$$$, we cannot choose any other node in that layer, since the $$$\text{MEX}$$$ will become $$$a_i$$$. Otherwise, if $$$a_i \gt m$$$, it is impossible for $$$m$$$ to be in that layer, since we know $$$a_i$$$ to be the minimum value in that layer.

Knowing this, how do we find the $$$\text{MEX}$$$? One solution is to put all the chosen elements in an array and check for the smallest missing value. Another option is to notice that since all values $$$0$$$ to $$$n + 1$$$ are present, the $$$\text{MEX}$$$ must be in one of the layers. Thus, you can simply look at the second smallest value for every layer — the smallest of these will be the $$$\text{MEX}$$$. The only edge case occurs when each layer consists of only one number; the answer is just $$$n + 2$$$.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int network[d + 2];
    network[0] = 0;
    network[d + 1] = n + 1;
    for (int i = 1; i <= d; i++) {
        int m;
        cin >> m;
        int smallest = n + 5;
        for (int j = 0; j < m; j++) {
            int v;
            cin >> v;
            smallest = min(smallest, v);
        }
        network[i] = smallest;
    }
    sort(network, network + d + 2);
    for (int i = 0; i < d + 2; i++) {
        if (network[i] != i) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << n + 2 << "\n";
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int ans = n + 2;
    for (int i = 0; i < d; i++) {
        int m;
        cin >> m;
        int s = n + 2;
        int ss = n + 2;
        for (int i = 0; i < m; i++) {
            int v;
            cin >> v;
            if (v < s) {
                ss = s;
                s = v;
            } else if (v < ss) ss = v;
        }
        ans = min(ans, ss);
    }
    cout << ans << "\n";
    return 0;
}

The amount of snow that accumulates on the tree is equal to the amount of snow that falls per day multiplied by the number of days it takes before the tree breaks.

The number of days before any individual node breaks is independent of the other nodes in the tree.

Each node will break after $$$\lfloor \frac{\text{strength}}{\text{weight of subtree}} \rfloor$$$ days. Greedily, it is optimal to strengthen the $$$k$$$ nodes which will break first. To calculate the weight of each node's subtree, we can use depth-first-search. Then, create an array storing each node's breaking point. Sort this array to determine the order in which to strengthen nodes.

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5;

int w[MAXN], a[MAXN], days[MAXN];
vector<int> adj[MAXN];

long long dfs(int i, int p){
    long long subtree = a[i];

    for(int j : adj[i]) if(j != p)
    	subtree += dfs(j, i);

    days[i] = w[i]/subtree;

    return subtree;
}

int main(){
    int n; cin >> n;

    for(int i=0; i<n; ++i) cin >> w[i];
    for(int i=0; i<n; ++i) cin >> a[i];

    for(int i=1; i<n; ++i){
    	int u, v; cin >> u >> v;
    	adj[u-1].push_back(v-1);
    	adj[v-1].push_back(u-1);
    }

    long long total = dfs(0, 0);

    sort(days, days+n);

    for(int i=0; i<n; ++i)
    	cout << total*days[i] << '\n';
}

Alice is able to determine what move Bob makes as Bob can only make one move to maximize the results.

Because Alice may choose only one entry of $$$A$$$, every other position has a fixed contribution we can precompute — specifically, how large the result would be if Bob chose that index after Alice's move. For any choice $$$i$$$ that Alice makes, Bob will pick whichever gives a larger value: either he picks $$$j = i$$$, or he picks the best index among all $$$j \neq i$$$. Alice's goal after that is to pick an index $$$i$$$ that minimizes this worse-case value.

To evaluate the best index among all $$$j \neq i$$$ efficiently for every i, we can compute the two largest values of $$$f(j) = A_j | (y-A_j)$$$ over all $$$j$$$. For a given index $$$i$$$, if the overall maximum $$$f(j)$$$ comes from $$$j = i$$$, then the best choice among the remaining indices is the second-largest. Otherwise, the best choice is the largest. Using this idea, we can check every $$$i$$$ in constant time after the initial scan, giving an $$$O(n)$$$ solution.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while(t--){
        int n; ll x, y;
        cin >> n >> x >> y;

        vector<ll> vals(n);
        ll sum = 0;
        for(int i = 0; i < n; ++i) {
            cin >> vals[i];
            sum += vals[i];
        }

        vector<ll> loss(n);
        for(int i = 0; i < n; ++i) loss[i] = vals[i]-(vals[i]&y);

        ll min1 = LLONG_MAX, min2 = LLONG_MAX;
        int idx1 = -1;
        for(int i = 0; i < n; ++i) {
            if(loss[i] < min1){
                min2 = min1;
                min1 = loss[i];
                idx1 = i;
            } else if(loss[i] < min2) {
                min2 = loss[i];
            }
        }

        ll ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            ll alice = vals[i]|x;
            ll delta = alice-vals[i], same = alice-(alice&y);
            ll obest = ((i == idx1) ? min2 : min1);
            ll bob = min(obest, same);
            ll temp = sum+delta-bob;
            ans = min(ans, temp);
        }

        cout << ans << "\n";
    }

    return 0;
}