比赛 2025.9.6 评测结果 AAAAAAAAAAAA
题目名称 Compatible Pairs 最终得分 100
用户昵称 秋_Water 运行时间 2.068 s
代码语言 C++ 内存使用 13.51 MiB
提交时间 2025-09-06 10:05:04
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
const int M=1e6+7;
#define ll long long
int n,a,b,w[N],d[N],in[N],h[M],cnt;
ll ans;
map<int,int>mapp;
struct edge{
	int to,nxt;
}e[M];
void addedge(int a,int b){
	e[++cnt].to=b;
	e[cnt].nxt=h[a];
	h[a]=cnt;
}
void add(int u,int v){
	addedge(u,v);
	addedge(v,u);
	in[u]++;
}
void topu(){
	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 vv=h[u];vv;vv=e[vv].nxt){
        	int v=e[vv].to;
			if(u==v){
				ans+=w[u]/2;
				w[u]%=2;
			}
			else if(w[v]>0){
				int res=min(w[u],w[v]);
				ans+=res;
				w[u]-=res;
				w[v]-=res;
			}
			in[v]--;
			if(in[v]==1){
				q.push(v);
			}
        }
    }	
}
int main(){
	freopen("Compatible.in","r",stdin);
	freopen("Compatible.out","w",stdout);
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>d[i];
		mapp[d[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(d[i]<=a&&mapp.count(a-d[i])){
			add(i,mapp[a-d[i]]);
		}
		if(a==b) continue;
		if(d[i]<=b&&mapp.count(b-d[i])){
			add(i,mapp[b-d[i]]);			
		}		
	}
	topu();
	cout<<ans;
	
	return 0;
}