A - What month is it?

A straightforward problem. The solution is to output ((x + y - 1) \mod 12 + 1).

B - Most Mniority

This problem can be solved with a brute-force approach. First, for each vote, count the number of votes for each option. Then, iterate through all participants and increment a counter for those who voted for the minority option in each vote.

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

int main() {
    int num_people, num_votes;
    cin >> num_people >> num_votes;
    vector<string> votes(num_people);
    for (int i = 0; i < num_people; i++) {
        cin >> votes[i];
    }
    
    vector<int> score(num_people, 0);
    for (int j = 0; j < num_votes; j++) {
        int count_zero = 0, count_one = 0;
        for (int i = 0; i < num_people; i++) {
            if (votes[i][j] == '0') count_zero++;
            else count_one++;
        }
        char minority_char = (count_zero < count_one) ? '0' : '1';
        for (int i = 0; i < num_people; i++) {
            if (votes[i][j] == minority_char) score[i]++;
        }
    }
    
    int max_score = *max_element(score.begin(), score.end());
    for (int i = 0; i < num_people; i++) {
        if (score[i] == max_score) cout << (i + 1) << " ";
    }
    cout << endl;
    return 0;
}

C - Sum of Min Query

Since each update modifies only one element, an online processing approach is suitable. Precompute the initial sum of the minimum values. For each update, subtract the current contribution of the element, apply the update, and then add the new contribution back to the sum.

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

int main() {
    int n, queries;
    cin >> n >> queries;
    vector<long long> arr_a(n), arr_b(n);
    for (int i = 0; i < n; i++) cin >> arr_a[i];
    for (int i = 0; i < n; i++) cin >> arr_b[i];
    
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += min(arr_a[i], arr_b[i]);
    }
    
    while (queries--) {
        char operation;
        int index, new_val;
        cin >> operation >> index >> new_val;
        index--;
        total -= min(arr_a[index], arr_b[index]);
        if (operation == 'A') arr_a[index] = new_val;
        else arr_b[index] = new_val;
        total += min(arr_a[index], arr_b[index]);
        cout << total << endl;
    }
    return 0;
}

D - Toggle Maze

This is a BFS problem with an additional state for the door toggle. Besides the coordinates (x, y), maintain a state t (0 or 1). When t=0, 'o' is passable and 'x' is blocked; when t=1, the opposite is true. The '?' tile toggles the state.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const long long INF = 1e18;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    int start_x, start_y, goal_x, goal_y;
    for (int i = 0; i < rows; i++) {
        cin >> grid[i];
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 'S') { start_x = i; start_y = j; }
            if (grid[i][j] == 'G') { goal_x = i; goal_y = j; }
        }
    }
    
    vector<vector<vector<long long>>> dist(rows, vector<vector<long long>>(cols, vector<long long>(2, INF)));
    queue<tuple<int, int, int>> q;
    dist[start_x][start_y][0] = 0;
    q.push({start_x, start_y, 0});
    
    int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    
    auto is_passable = [](char cell, int state) -> bool {
        if (cell == '#') return false;
        if (cell == '.' || cell == 'S' || cell == 'G' || cell == '?') return true;
        if (cell == 'o') return state == 0;
        if (cell == 'x') return state == 1;
        return false;
    };
    
    while (!q.empty()) {
        auto [x, y, t] = q.front(); q.pop();
        long long current_dist = dist[x][y][t];
        if (x == goal_x && y == goal_y) {
            cout << current_dist << endl;
            return 0;
        }
        for (auto [dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
            if (!is_passable(grid[nx][ny], t)) continue;
            int new_state = t;
            if (grid[nx][ny] == '?') new_state ^= 1;
            if (dist[nx][ny][new_state] > current_dist + 1) {
                dist[nx][ny][new_state] = current_dist + 1;
                q.push({nx, ny, new_state});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

E - Reachability Query

This problem involves an undirected graph where edges are added and node colors are toggled. A Union-Find (Disjoint Set Union) data structure is appropriate. For each connected component, track the count of black nodes. Toggling a node's color updates this count. A query checks if the componetn containing a node has any black nodes.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

struct DisjointSet {
    vector<int> parent, size, black_count;
    DisjointSet(int n) : parent(n+1), size(n+1, 1), black_count(n+1, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_sets(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        black_count[a] += black_count[b];
    }
    void mark_black(int x) { black_count[find(x)]++; }
    void unmark_black(int x) { black_count[find(x)]--; }
    bool has_black(int x) { return black_count[find(x)] > 0; }
};

int main() {
    int n, q;
    cin >> n >> q;
    DisjointSet dsu(n);
    vector<int> color(n+1, 0);
    
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int u, v; cin >> u >> v;
            dsu.union_sets(u, v);
        } else if (type == 2) {
            int x; cin >> x;
            if (color[x] == 0) {
                color[x] = 1;
                dsu.mark_black(x);
            } else {
                color[x] = 0;
                dsu.unmark_black(x);
            }
        } else {
            int x; cin >> x;
            cout << (dsu.has_black(x) ? "Yes" : "No") << endl;
        }
    }
    return 0;
}