Submission #1230652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230652		jajskao	Colouring a rectangle (eJOI19_colouring)	C++20	60 / 100	225 ms	167936 KiB

colouring

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

// Use a large enough value for infinity in the context of the problem's costs.
const long long INF = 4e14; // Sum of all possible costs is approx 2e5*2*1e9 = 4e14

struct Edge {
    int to;
    long long capacity;
    int rev;
};

vector<vector<Edge>> adj;
vector<int> level;
vector<int> iter;

// Adds a directed edge from u to v with a certain capacity.
void add_edge(int u, int v, long long cap) {
    adj[u].push_back({v, cap, (int)adj[v].size()});
    adj[v].push_back({u, 0, (int)adj[u].size() - 1}); // Residual edge
}

// Builds the level graph using BFS for Dinic's algorithm.
bool bfs(int s, int t) {
    level.assign(adj.size(), -1);
    vector<int> q;
    q.push_back(s);
    level[s] = 0;
    int head = 0;
    while(head < q.size()){
        int u = q[head++];
        for(const auto& edge : adj[u]){
            if(edge.capacity > 0 && level[edge.to] < 0){
                level[edge.to] = level[u] + 1;
                q.push_back(edge.to);
            }
        }
    }
    return level[t] != -1;
}

// Finds an augmenting path using DFS on the level graph.
long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    for (int& i = iter[u]; i < adj[u].size(); ++i) {
        Edge& e = adj[u][i];
        if (e.capacity > 0 && level[u] < level[e.to]) {
            long long d = dfs(e.to, t, min(f, e.capacity));
            if (d > 0) {
                e.capacity -= d;
                adj[e.to][e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

// Computes the maximum flow from s to t using Dinic's algorithm.
long long max_flow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
        iter.assign(adj.size(), 0);
        long long f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

// Globals to be used by the segment tree functions
int m, n;
vector<int> lr_node_indices_global;
int seg_tree_nodes_start_global;

// Recursively builds the segment tree for min-cut graph optimization.
void build_seg_tree(int u, int l, int r) {
    if (l == r) {
        add_edge(seg_tree_nodes_start_global + u, lr_node_indices_global[l], INF);
        return;
    }
    int mid = l + (r - l) / 2;
    // Edges from parent to children in the segment tree
    add_edge(seg_tree_nodes_start_global + u, seg_tree_nodes_start_global + 2 * u, INF);
    add_edge(seg_tree_nodes_start_global + u, seg_tree_nodes_start_global + 2 * u + 1, INF);
    build_seg_tree(2 * u, l, mid);
    build_seg_tree(2 * u + 1, mid + 1, r);
}

// Adds edges from a source node to the segment tree nodes covering a target range.
void add_range_edges(int u, int l, int r, int target_l, int target_r, int from_node) {
    if (r < target_l || l > target_r) return;
    if (target_l <= l && r <= target_r) {
        add_edge(from_node, seg_tree_nodes_start_global + u, INF);
        return;
    }
    int mid = l + (r - l) / 2;
    add_range_edges(2 * u, l, mid, target_l, target_r, from_node);
    add_range_edges(2 * u + 1, mid + 1, r, target_l, target_r, from_node);
}

// Solves one of the two independent subproblems (even or odd parity).
long long solve_subproblem(const vector<pair<int, int>>& lr_diags, const vector<pair<int, int>>& rl_diags) {
    if (lr_diags.empty() || rl_diags.empty()) {
        return 0;
    }

    int p = lr_diags.size();
    int q = rl_diags.size();

    map<int, int> lr_id_to_idx;
    for (int i = 0; i < p; ++i) {
        lr_id_to_idx[lr_diags[i].first] = i;
    }
    
    // Define node indices for the graph
    int s = 0;
    int rl_nodes_start = 1;
    int lr_nodes_raw_start = rl_nodes_start + q;
    seg_tree_nodes_start_global = lr_nodes_raw_start + p;
    int seg_tree_size = 4 * p;
    int t = seg_tree_nodes_start_global + seg_tree_size;
    int num_nodes = t + 1;

    adj.assign(num_nodes, vector<Edge>());
    
    // Set up global variables for segment tree construction
    lr_node_indices_global.resize(p);
    iota(lr_node_indices_global.begin(), lr_node_indices_global.end(), lr_nodes_raw_start);
    
    // Add edges from source to RL-diagonal nodes
    for (int i = 0; i < q; ++i) {
        add_edge(s, rl_nodes_start + i, rl_diags[i].second);
    }

    // Add edges from LR-diagonal nodes to sink
    for (int i = 0; i < p; ++i) {
        add_edge(lr_nodes_raw_start + i, t, lr_diags[i].second);
    }
    
    // Build the segment tree over LR-diagonal nodes
    if (p > 0) {
        build_seg_tree(1, 0, p - 1);
    }

    // Connect RL-diagonal nodes to the segment tree
    for (int i = 0; i < q; ++i) {
        int d_rl = rl_diags[i].first;
        
        long long drl_ll = d_rl;
        long long n_ll = n;
        long long m_ll = m;
        
        // Calculate the range of LR-diagonal IDs that this RL-diagonal intersects
        long long d_lr_min = max(-drl_ll, drl_ll - 2 * n_ll + 2);
        long long d_lr_max = min(drl_ll, 2 * m_ll - 2 - drl_ll);

        auto it_min = lr_id_to_idx.lower_bound(d_lr_min);
        if (it_min == lr_id_to_idx.end() || it_min->first > d_lr_max) continue;
        
        auto it_max = lr_id_to_idx.upper_bound(d_lr_max);
        it_max--;
        
        int idx_min = it_min->second;
        int idx_max = it_max->second;
        
        if (idx_min > idx_max) continue;

        add_range_edges(1, 0, p - 1, idx_min, idx_max, rl_nodes_start + i);
    }

    return max_flow(s, t);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m >> n;

    vector<int> lr_costs(m + n - 1);
    vector<int> rl_costs(m + n - 1);

    for (int i = 0; i < m + n - 1; ++i) cin >> lr_costs[i];
    for (int i = 0; i < m + n - 1; ++i) cin >> rl_costs[i];

    vector<pair<int, int>> lr_even, lr_odd;
    vector<pair<int, int>> rl_even, rl_odd;

    // Partition diagonals by parity
    for (int i = 0; i < m + n - 1; ++i) {
        int id = i + 1 - n; // As per problem statement indexing
        if (abs(id) % 2 == 0) {
            lr_even.push_back({id, lr_costs[i]});
        } else {
            lr_odd.push_back({id, lr_costs[i]});
        }
    }

    for (int i = 0; i < m + n - 1; ++i) {
        int id = i; // As per problem statement indexing
        if (id % 2 == 0) {
            rl_even.push_back({id, rl_costs[i]});
        } else {
            rl_odd.push_back({id, rl_costs[i]});
        }
    }

    long long total_cost = 0;
    total_cost += solve_subproblem(lr_even, rl_even);
    total_cost += solve_subproblem(lr_odd, rl_odd);

    cout << total_cost << endl;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20