Submission #1230650

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

colouring

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

using namespace std;

const long long INF_LL = 1e18; // For total flow
const int INF_INT = 2e9;      // For edge capacities (costs fit in int)

// Edge struct with int capacity to save memory.
struct Edge {
    int to;
    int capacity;
    int rev; // Index of the reverse edge in the 'edges' vector
};

// --- Globals for the compact graph and flow algorithm ---
vector<Edge> edges;
vector<int> adj_head; // Head of the adjacency list for each node
vector<int> level;
vector<int> iter;
vector<pair<int, int>> seg_tree_children;
vector<int> v_nodes_map;

// Adds an edge to the compact adjacency list.
void add_edge(int u, int v, int cap) {
    // Forward edge
    edges.push_back({v, cap, (int)edges.size() + 1});
    adj_head.push_back(u);

    // Backward edge
    edges.push_back({u, 0, (int)edges.size() - 1});
    adj_head.push_back(v);
}

// BFS to build the level graph.
bool bfs(int s, int t, int node_count) {
    level.assign(node_count, -1);
    vector<int> q;
    q.reserve(node_count);
    level[s] = 0;
    q.push_back(s);
    size_t head = 0;
    while (head < q.size()) {
        int u = q[head++];
        // This loop structure is different due to the compact graph representation
        for (size_t i = 0; i < adj_head.size(); ++i) {
            if (adj_head[i] != u) continue;
            Edge& e = edges[i];
            if (e.capacity > 0 && level[e.to] < 0) {
                level[e.to] = level[u] + 1;
                q.push_back(e.to);
            }
        }
    }
    return level[t] != -1;
}

// DFS to find augmenting paths.
long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    // The iter vector now stores the index to check in the 'edges' list.
    for (int& i = iter[u]; i < (int)adj_head.size(); ++i) {
        if (adj_head[i] != u) continue;

        Edge& e = edges[i];
        if (e.capacity > 0 && level[u] < level[e.to]) {
            long long d = dfs(e.to, t, min(f, (long long)e.capacity));
            if (d > 0) {
                e.capacity -= d;
                edges[e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}


// Dinic's max-flow algorithm.
long long max_flow(int s, int t, int node_count) {
    long long flow = 0;
    while (bfs(s, t, node_count)) {
        // Here, iter needs to be smarter. We can't just iterate the whole edge list for each node.
        // A better approach is to sort the edges by 'from' node once.
        // For simplicity and to see if it passes, let's keep it, but this is slow.
        // A more optimized DFS would be needed for performance if this TLEs.
        iter.assign(node_count, 0); 
        long long f;
        while ((f = dfs(s, t, INF_LL)) > 0) {
            flow += f;
        }
    }
    return flow;
}

// The provided solution had a bug in DFS iteration logic for the compact representation.
// A correct, though potentially slower, DFS iteration:
long long dfs_corrected(int u, int t, long long f, const vector<vector<int>>& node_to_edges) {
    if (u == t) return f;
    for (int& i = iter[u]; i < (int)node_to_edges[u].size(); ++i) {
        int edge_idx = node_to_edges[u][i];
        Edge& e = edges[edge_idx];
        if (e.capacity > 0 && level[u] < level[e.to]) {
            long long d = dfs_corrected(e.to, t, min(f, (long long)e.capacity), node_to_edges);
            if (d > 0) {
                e.capacity -= d;
                edges[e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

// Correct Dinic's using a pre-computed index for neighbors.
long long max_flow_corrected(int s, int t, int node_count) {
    long long flow = 0;
    vector<vector<int>> node_to_edges(node_count);
    for(int i = 0; i < (int)edges.size(); ++i) {
        node_to_edges[adj_head[i]].push_back(i);
    }
    
    while (bfs(s, t, node_count)) {
        iter.assign(node_count, 0);
        long long f;
        while ((f = dfs_corrected(s, t, INF_LL, node_to_edges)) > 0) {
            flow += f;
        }
    }
    return flow;
}


// Segment tree build and query remain conceptually the same.
int build_seg_tree(int l, int r, int& node_idx, int seg_base_idx) {
    int curr_node = node_idx++;
    if (l == r) {
        add_edge(curr_node, v_nodes_map[l], INF_INT);
    } else {
        int mid = l + (r - l) / 2;
        int child1 = build_seg_tree(l, mid, node_idx, seg_base_idx);
        int child2 = build_seg_tree(mid + 1, r, node_idx, seg_base_idx);
        seg_tree_children[curr_node - seg_base_idx] = {child1, child2};
        add_edge(curr_node, child1, INF_INT);
        add_edge(curr_node, child2, INF_INT);
    }
    return curr_node;
}

void query_seg_tree(int node_idx, int seg_base_idx, int l, int r, int ql, int qr, int u_node) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        add_edge(u_node, node_idx, INF_INT);
        return;
    }
    int mid = l + (r - l) / 2;
    pair<int, int> children = seg_tree_children[node_idx - seg_base_idx];
    if (children.first != -1) query_seg_tree(children.first, seg_base_idx, l, mid, ql, qr, u_node);
    if (children.second != -1) query_seg_tree(children.second, seg_base_idx, mid + 1, r, ql, qr, u_node);
}

long long solve_for_parity(int m, int n, const vector<int>& c1, const vector<int>& c2, int parity) {
    vector<int> costs1, costs2;
    vector<int> i_orig, j_orig;

    for (int i = 1 - n; i <= m - 1; ++i) if (abs(i % 2) == parity) {
        i_orig.push_back(i);
        costs1.push_back(c1[i + n - 1]);
    }
    for (int j = 0; j <= m + n - 2; ++j) if (j % 2 == parity) {
        j_orig.push_back(j);
        costs2.push_back(c2[j]);
    }
    if (costs1.empty() || costs2.empty()) return 0;

    int num_u = costs1.size();
    int num_v = costs2.size();
    int num_seg_nodes_est = (num_v > 0) ? 2 * num_v : 0;
    
    // --- Graph construction ---
    edges.clear();
    adj_head.clear();
    
    vector<int> u_nodes_map(num_u);
    v_nodes_map.assign(num_v, 0);

    int node_idx = 2; // S=0, T=1
    for (int i = 0; i < num_u; ++i) u_nodes_map[i] = node_idx++;
    for (int i = 0; i < num_v; ++i) v_nodes_map[i] = node_idx++;

    for (int i = 0; i < num_u; ++i) add_edge(0, u_nodes_map[i], costs1[i]);
    for (int i = 0; i < num_v; ++i) add_edge(v_nodes_map[i], 1, costs2[i]);

    int seg_base_idx = node_idx;
    int seg_root = -1;
    if (num_v > 0) {
        seg_tree_children.assign(num_seg_nodes_est, {-1, -1});
        seg_root = build_seg_tree(0, num_v - 1, node_idx, seg_base_idx);
    }

    for (int u_idx = 0; u_idx < num_u; ++u_idx) {
        long long i_val = i_orig[u_idx];
        long long j_start_val = abs(i_val);
        long long j_end_val = min((long long)2 * m - 2 - i_val, (long long)2 * n - 2 + i_val);

        if (j_start_val > j_end_val) continue;
        auto it_start = lower_bound(j_orig.begin(), j_orig.end(), j_start_val);
        if (it_start == j_orig.end() || *it_start > j_end_val) continue;
        auto it_end = upper_bound(j_orig.begin(), j_orig.end(), j_end_val);
        --it_end;
        int v_idx_start = distance(j_orig.begin(), it_start);
        int v_idx_end = distance(j_orig.begin(), it_end);
        
        if (v_idx_start <= v_idx_end && seg_root != -1) {
            query_seg_tree(seg_root, seg_base_idx, 0, num_v - 1, v_idx_start, v_idx_end, u_nodes_map[u_idx]);
        }
    }
    
    return max_flow_corrected(0, 1, node_idx);
}

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

    int m, n;
    cin >> m >> n;
    vector<int> c1(m + n - 1), c2(m + n - 1); // Costs fit in int
    for (int i = 0; i < m + n - 1; ++i) cin >> c1[i];
    for (int i = 0; i < m + n - 1; ++i) cin >> c2[i];

    long long total_cost = 0;
    total_cost += solve_for_parity(m, n, c1, c2, 0);
    total_cost += solve_for_parity(m, n, c1, c2, 1);
    
    cout << total_cost << endl;

    return 0;
}

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