Submission #1230642

#TimeUsernameProblemLanguageResultExecution timeMemory
1230642brito.joaoColouring a rectangle (eJOI19_colouring)C++20
60 / 100
198 ms167936 KiB
#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; const long long INF = 1e18; // Structure to represent a directed edge in the flow network struct Edge { int to; long long capacity; int rev; // Index of the reverse edge in the adjacency list of 'to' }; vector<vector<Edge>> adj; vector<int> level; vector<size_t> iter; vector<pair<int, int>> seg_tree_children; // Stores children for segment tree nodes vector<int> v_nodes; // Stores the indices of v-nodes for one parity // Adds a directed edge and its residual edge 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}); } // BFS to build the level graph 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; size_t 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; } // DFS to find augmenting paths in the level graph long long dfs(int u, int t, long long f) { if (u == t) return f; for (size_t& 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; } // Dinic's max-flow 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; } int build_seg_tree(int l, int r, int& node_idx) { int curr_node = node_idx++; seg_tree_children.emplace_back(-1, -1); if (l == r) { add_edge(curr_node, v_nodes[l], INF); } else { int mid = l + (r - l) / 2; int child1 = build_seg_tree(l, mid, node_idx); int child2 = build_seg_tree(mid + 1, r, node_idx); seg_tree_children[curr_node - (int)v_nodes.back() - 1] = {child1, child2}; add_edge(curr_node, child1, INF); add_edge(curr_node, child2, INF); } 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); 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); 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<long long>& c1, const vector<long long>& c2, int parity) { vector<long long> 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 = 4 * num_v; int total_nodes = 2 + num_u + num_v + num_seg_nodes_est; adj.assign(total_nodes, vector<Edge>()); int S = 0, T = 1; vector<int> u_nodes(num_u); v_nodes.assign(num_v, 0); int node_idx = 2; for (int i = 0; i < num_u; ++i) u_nodes[i] = node_idx++; for (int i = 0; i < num_v; ++i) v_nodes[i] = node_idx++; for (int i = 0; i < num_u; ++i) add_edge(S, u_nodes[i], costs1[i]); for (int i = 0; i < num_v; ++i) add_edge(v_nodes[i], T, costs2[i]); int seg_base_idx = node_idx; seg_tree_children.clear(); if(num_v > 0) seg_tree_children.reserve(num_seg_nodes_est); int seg_root = -1; if (num_v > 0) { seg_root = build_seg_tree(0, num_v - 1, node_idx); } if(num_v > 0) seg_tree_children.resize(node_idx - seg_base_idx); for (int u_idx = 0; u_idx < num_u; ++u_idx) { int i_val = i_orig[u_idx]; long long j_start_val = max((long long)i_val, (long long)-i_val); long long j_end_val = min(2LL * m - 1 - i_val, 2LL * n - 1 + 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; int v_idx_start = distance(j_orig.begin(), it_start); auto it_end = upper_bound(j_orig.begin(), j_orig.end(), j_end_val); --it_end; 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[u_idx]); } } adj.resize(node_idx); return max_flow(S, T); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m, n; cin >> m >> n; vector<long long> c1(m + n - 1), c2(m + n - 1); 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); // Even parity total_cost += solve_for_parity(m, n, c1, c2, 1); // Odd parity cout << total_cost << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...