CF40E

The problem involves a combinatorial proof regarding parity conditions.

Lemma 1: If the answer is non-zero, then n and m must have the same parity.

Proof: Considering each row and column sums to 1, multiplying all entries yields (-1)^n = (-1)^m, hence n ≡ m (mod 2).

Lemma 2: Under Lemma 1's condition, if all columns satisfy the constraint and all rows except one do, then that row also satisfies it. The proof mirrors the previous argument.

The key observation is that when k < max(n, m), atleast one row remains unfilled. Assuming other rows are valid, the remaining row must also be valid due to the constraints and Lemma 2.

We compute the number of ways to fill each row excluding one special row (mex). For each row i, the number of possibilities is 2^(m - count(i) - 1).

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

const int N = 1e3 + 5;
int n, m, k, flag, Mod, mex, ans, qpow[N], cnt[N], val[N];

signed main(){
    cin >> n >> m >> k;
    if(k >= n) flag = 1, swap(n, m);
    for(int i = 1; i <= k; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(flag) swap(x, y);
        cnt[x]++;
        val[x] = val[x] == 0 ? z : val[x] * z;
    }
    mex = 1; while(cnt[mex]) mex++;
    cin >> Mod;
    
    qpow[0] = 1;
    for(int i = 1; i <= max(n, m); i++) qpow[i] = qpow[i - 1] * 2 % Mod;
    ans = !(((n & 1) ^ (m & 1)) & 1);
    for(int i = 1; i <= n; i++){
        if(i == mex) continue;
        if(cnt[i] == m && val[i] == 1) ans = 0;
        if(cnt[i] ^ m) ans = (ans * qpow[m - cnt[i] - 1]) % Mod;
    }
    cout << ans << endl;
    return 0;
}

ARC076E

This problem deals with edge orientation in a grid where we consider only edges whose endpoints lie on the boundary.

Each edge is mapped to a linear value based on its position around the rectangle. We use a stack to simulate the traversal of these values, ensuring no two adjacent edges share the same color.

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

const int N = 1e7;
int r, c, n, tmp, poscnt, st[N], top;

struct node{
    int val, color;
}pos[N];

bool cmp(node a, node b){
    return a.val < b.val;
}

node makeNode(int val, int color){
    node res;
    res.val = val;
    res.color = color;
    return res;
}

signed main(){
    cin >> r >> c >> n;
    for(int i = 1; i <= n; i++){
        int ax, ay, bx, by;
        cin >> ax >> ay >> bx >> by;
        if(ax != 0 && ay != 0 && ax != r && ay != c) continue;
        if(bx != 0 && by != 0 && bx != r && by != c) continue;
        
        if(ay == 0) tmp = ax;
        else if(ax == r) tmp = r + ay;
        else if(ay == c) tmp = 2 * r + c - ax;
        else tmp = 2 * r + 2 * c - ay;
        pos[++poscnt] = makeNode(tmp, i);
        
        if(by == 0) tmp = bx;
        else if(bx == r) tmp = r + by;
        else if(by == c) tmp = 2 * r + c - bx;
        else tmp = 2 * r + 2 * c - by;
        pos[++poscnt] = makeNode(tmp, i);
    }
    
    sort(pos + 1, pos + 1 + poscnt, cmp);
    
    for(int i = 1; i <= poscnt; i++){
        if(st[top] == pos[i].color) top--;
        else st[++top] = pos[i].color;
    }
    
    cout << (top ? "NO" : "YES") << endl;
    return 0;
}

AGC035B

A graph orientation problem involving making all degrees even.

For trees, we perform a DFS from leaves upward, adjusting edges to ensure the degree of each node is even. This approach extends to general graphs by constructing a spanning tree and orienting the remaining edges arbitrarily.

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

const int N = 2e5;
int n, m, x[N], y[N], used[N], deg[N];
vector<int> g[N];
map<pair<int, int>, short> dir;

void dfs(int u, int pre){
    used[u] = 1;
    for(int v : g[u]){
        if(used[v]){
            if(v == pre || dir[make_pair(u, v)]) continue;
            dir[make_pair(u, v)] = 1, dir[make_pair(v, u)] = 2;
            deg[u]++;
            continue;
        }
        dfs(v, u);
    }
    if(!pre) return ;
    if(deg[u] & 1){
        dir[make_pair(u, pre)] = 1, dir[make_pair(pre, u)] = 2;
        deg[u]++;
    }
    else{
        dir[make_pair(u, pre)] = 2, dir[make_pair(pre, u)] = 1;
        deg[pre]++;
    }
    return ;
}

int main(){
    cin >> n >> m;
    if(m & 1){cout << -1 << endl; return 0;}
    
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> y[i];
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    
    dfs(1, 0);
    
    for(int i = 1; i <= m; i++){
        if(dir[make_pair(x[i], y[i])] == 2) cout << y[i] << " " << x[i] << endl;
        else cout << x[i] << " " << y[i] << endl;
    }
    return 0;
}