记录编号	605665	评测结果	AAAAAAAAAAAA
题目名称	4171.[USACO25 Open Silver]Compatible Pairs	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	2.219 s
提交时间	2025-09-06 12:06:27	内存使用	16.06 MiB

#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;

#define int long long

const int MAXM = 1e6 + 5;
const int MAXN= 2 * 1e5 + 5;
int N, A, B;
struct node{
	int to, next;
}e[MAXM];
int val[MAXN], sum[MAXN];
int in[MAXN], id[MAXN];
int h[MAXN];
unordered_map<int, int> index;
int tot = 0, ans = 0;

void add(int x, int y){
	e[++ tot] = {y, h[x]};
	h[x] = tot; in[x] ++;
}

void Topsort(){
	queue<int> q;
	for(int i = 1;i <= N;i ++){
		if(in[i] == 1) q.push(i);
	}
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = h[u];i;i = e[i].next){
			int v = e[i].to;
			if(u == v){
				ans += (val[u] >> 1);
				val[u] = val[u] & 1;
			}
			else if(val[v] > 0){
				int cut = min(val[u], val[v]);
				val[u] -= cut, val[v] -= cut;
				ans += cut;
				q.push(v);
			}
		}
	}
}

signed main(){
	freopen("Compatible.in", "r", stdin);
	freopen("Compatible.out", "w", stdout);
	cin >> N >> A >> B;
	
	for(int i = 1;i <= N;i ++){
		cin >> val[i] >> id[i];
		index[id[i]] = i;
	}
	
	for(int i = 1;i <= N;i ++){
		int ID = id[i];
		if(ID <= A && index[A - ID]) add(i, index[A - ID]);
		if(A != B && ID <= B && index[B - ID]) add(i, index[B - ID]);
	}
	
	Topsort();
	
	cout << ans << '\n';
	
	return 0;
}