Submission #1268925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268925		TIN	Domino (COCI15_domino)	C++17	150 / 160	402 ms	114792 KiB

domino

#include <bits/stdc++.h>

#define FNAME "test"

using namespace std;

template<typename T> using min_heap = priority_queue<T,vector<T>,greater<T>>;

template<class X, class Y>
bool minimize(X& x, const Y& y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}

template<class Cost, class Flow>
class MinCostFlow {
private:
	struct Edge {
		int from, to;
		Flow capa, flow;
		Cost cost;

		Edge(int _from, int _to, Flow _capa, Cost _cost) {
			from = _from; to = _to;
			capa = _capa; flow = Flow(0);
			cost = _cost;
		}

		Flow residual() const {
			return capa - flow;
		}
	};

	int numNode;
	vector<Edge> edges;
	vector<vector<int>> adj;
	vector<Cost> dist;
	vector<int> par;
	vector<bool> inQueue;

	bool fordBellman(int source, int sink) {
		fill(dist.begin(), dist.end(), numeric_limits<Cost>::max());
		fill(par.begin(), par.end(), -1);
		fill(inQueue.begin(), inQueue.end(), false);
		queue<int> q;
		dist[source] = 0; q.push(source); inQueue[source] = true;
		while (!q.empty()) {
			int u = q.front(); q.pop(); inQueue[u] = false;
			for (int edgeID : adj[u]) if (edges[edgeID].residual() > Flow(0)) {
				int v = edges[edgeID].to;
				Cost cost = edges[edgeID].cost;
				if (minimize(dist[v], dist[u] + cost)) {
					par[v] = edgeID;
					if (!inQueue[v]) {
						q.push(v);
						inQueue[v] = true;
					}
				}
			}
		}
		return dist[sink] < numeric_limits<Cost>::max();
	}
public:
	MinCostFlow(int _numNode = 0) {
		numNode = _numNode;
		edges.clear();
		adj.assign(_numNode, vector<int>());
		dist.assign(_numNode, Cost(0));
		par.assign(_numNode, -1);
		inQueue.assign(_numNode, false);
	}

	void addEdge(int from, int to, Flow capa, Cost cost) {
		adj[from].push_back(edges.size());
		edges.push_back(Edge(from, to, capa, cost));
		adj[to].push_back(edges.size());
		edges.push_back(Edge(to, from, Flow(0), -cost));
	}

	pair<Cost,Flow> getMCMF(int source, int sink, Flow desiredFlow = numeric_limits<Flow>::max()) {
		Cost totalCost = Cost(0);
		Flow totalFlow = Flow(0);
		while (fordBellman(source, sink) && totalFlow < desiredFlow) {
			Flow delta = desiredFlow - totalFlow;
			for (int node = sink; node != source; node = edges[par[node]].from)
				minimize(delta, edges[par[node]].residual());
			totalFlow += delta;
			totalCost += dist[sink] * Cost(delta);
			for (int node = sink; node != source; node = edges[par[node]].from) {
				edges[par[node]].flow += delta;
				edges[par[node] ^ 1].flow -= delta;
			}
		}
		if (desiredFlow != numeric_limits<Flow>::max()) {
			if (totalFlow != desiredFlow) {
				totalFlow = -1;
			}
		}
		return make_pair(totalCost, totalFlow);
	}
};

void Task() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Solve() {
	int tableSize, numDomino;
	cin >> tableSize >> numDomino;
	vector<vector<int>> grid(tableSize, vector<int>(tableSize));
	for (int row = 0; row < tableSize; ++row) {
		for (int col = 0; col < tableSize; ++col) {
			cin >> grid[row][col];
		}
	}
	auto cellID = [&](int row, int col) -> int {
		return row * tableSize + col;
	};
	min_heap<pair<int,pair<int,int>>> pq;
	int ans = 0;
	for (int row = 0; row < tableSize; ++row) {
		for (int col = 0; col < tableSize; ++col) {
			ans += grid[row][col];
			if ((row + col) % 2 == 1) continue;
			if (row - 1 >= 0) {
				int cost = -(grid[row][col] + grid[row - 1][col]);
				pq.push({cost, {cellID(row,col), cellID(row - 1, col)}});
			}
			if (row + 1 < tableSize) {
				int cost = -(grid[row][col] + grid[row + 1][col]);
				pq.push({cost, {cellID(row,col), cellID(row + 1, col)}});
			}
			if (col - 1 >= 0) {
				int cost = -(grid[row][col] + grid[row][col - 1]);
				pq.push({cost, {cellID(row,col), cellID(row, col - 1)}});
			}
			if (col + 1 < tableSize) {
				int cost = -(grid[row][col] + grid[row][col + 1]);
				pq.push({cost, {cellID(row,col), cellID(row, col + 1)}});
			}
		}
	}
	int numNeed = min(8 * numDomino, (int) pq.size());
	vector<pair<int,pair<int,int>>> edges;
	for (int i = 1; i <= numNeed; ++i) {
		edges.push_back(pq.top());
		pq.pop();
	}
	vector<int> vec;
	for (auto e : edges) {
		vec.push_back(e.second.first);
		vec.push_back(e.second.second);
	}
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	int numNode = (int) vec.size() + 2;
	vector<int> halfA, halfB;
	for (auto& e : edges) {
		e.second.first = lower_bound(vec.begin(), vec.end(), e.second.first) - vec.begin() + 1;
		halfA.push_back(e.second.first);
		e.second.second = lower_bound(vec.begin(), vec.end(), e.second.second) - vec.begin() + 1;
		halfB.push_back(e.second.second);
	}
	for (int _ = 0; _ < 2; _++) {
		sort(halfA.begin(), halfA.end());
		halfA.resize(unique(halfA.begin(), halfA.end()) - halfA.begin());
		swap(halfA, halfB);
	}
	MinCostFlow<int,int> solver(numNode);
	int source = 0, sink = numNode - 1;
	for (int node : halfA) solver.addEdge(source, node, 1, 0);
	for (auto e : edges) solver.addEdge(e.second.first, e.second.second, 1, e.first);
	for (int node : halfB) solver.addEdge(node, sink, 1, 0);
	int totalCost, totalFlow;
	tie(totalCost, totalFlow) = solver.getMCMF(source, sink, numDomino);
	ans += totalCost;
	cout << ans;
}

int main() {
	Task();
	Solve();
	return 0;
}

Compilation message (stderr)

domino.cpp: In function 'void Task()':
domino.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 10 / 10