Consider an undirected graph with a vertex for every distinct ID that appears in the input. Draw an edge (possibly a self-loop) between every two vertices whose labels sum to A or B. Then cows can only be paired if their vertices are connected by an edge, and every vertex is incident to at most two distinct edges. For each edge, we need to choose some non-negative number of pairs to form along it such that no ID is used more times than it appears.
Graph Theory Definitions: We say that
This runs in O(NlogN) if a sorted map is used.
#include <bits/stdc++.h> using namespace std; template <class T> using V = vector<T>; #define all(x) begin(x), end(x) int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, A, B; cin >> N >> A >> B; assert(A == B); map<int, int> cnt; while (N--) { int n, id; cin >> n >> id; cnt[id] = n; } int64_t ans = 0; for (auto [id, n] : cnt) { if (2 * id < A) { if (cnt.count(A - id)) ans += min(n, cnt.at(A - id)); } else if (2 * id == A) { ans += n / 2; } } cout << ans << "\n"; }
It turns out that as long as we repeat the procedure above while possible, we will end up removing all edges from the graph (see the end of the analysis for why).
To simulate this efficiently, we can maintain a list of vertices that might be incident to exactly one edge. While the list is nonempty, we can remove its last element, and if this element is incident to exactly one edge, apply the procedure above and append y to the list.
The runtime is O(NlogN), which is the same as the previous subtask. Solutions with an additional factor of N could receive partial credit.
#include <bits/stdc++.h> using namespace std; template <class T> using V = vector<T>; #define all(x) begin(x), end(x) int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, A, B; cin >> N >> A >> B; map<int, int> cnt; while (N--) { int n, id; cin >> n >> id; cnt[id] = n; } map<int, set<int>> adj; vector<int> cands; for (auto [id, _] : cnt) { cands.push_back(id); adj[id] = {}; for (int s : {A, B}) if (cnt.count(s - id)) adj[id].insert(s - id); } int64_t ans = 0; while (!cands.empty()) { int x = cands.back(); cands.pop_back(); if (adj.at(x).size() != 1) continue; int y = *begin(adj.at(x)); if (x == y) { ans += cnt.at(x) / 2; } else { int pairs = min(cnt.at(x), cnt.at(y)); ans += pairs; cnt.at(y) -= pairs; } // note: cnt[x] is no longer used in any future steps, // so its value doesn't matter adj.at(x).erase(y); adj.at(y).erase(x); cands.push_back(y); } // sanity check: no edges remaining for (const auto &[id, s] : adj) assert(s.empty()); cout << ans << "\n"; }
It remains to consider A≠B. Every vertex in the graph incident to at least one edge must be incident to either one or two edges. Suppose there is a vertex x incident to two edges (one corresponding to summing to A, and the other corresponding to summing to B). Then let's construct a walk by traversing a type-A edge, then a type-B edge, then a type-A edge, and so forth. This walk will eventually terminate at some vertex incident to exactly one edge. or it would run indefinitely. However, the latter case is impossible since then it would traverse infinitely many distinct vertices (x,x+B−A,x+2(B−A),…), contradicting the graph having finite size.