比赛 2025.9.6 评测结果 AAWWWWWWWWWW
题目名称 Compatible Pairs 最终得分 17
用户昵称 李金泽 运行时间 1.338 s
代码语言 C++ 内存使用 12.98 MiB
提交时间 2025-09-06 11:54:13
显示代码纯文本
#include<cstdio>
#include<queue>
#include<unordered_map>
#define N 200005
using namespace std;
int n,a,b,h[N],cnt,f[N],d[N],s[N],o[N],x,ans;bool vis[N];
struct edge{int v,n;}e[N<<2];
void ad(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;o[v]++;}
queue<int>q; 
unordered_map<int,int>mp;
int min(int x,int y){return x<y?x:y;}
int read(){
	int sum=0;bool f=0;char c=getchar();
	for(;c<48||c>57;c=getchar())if(c==45)f=1;
	for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
	return f?-sum:sum;
}
int main(){
	freopen("Compatible.in","r",stdin);freopen("Compatible.out","w",stdout);
	n=read(),a=read(),b=read();
	for(int i=1;i<=n;i++)
	{
		s[i]=read();d[i]=read();
		mp[d[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(x=mp[a-d[i]])ad(i,x);
		if(a^b&&(x=mp[b-d[i]]))ad(i,x);
	}
	for(int i=1;i<=n;i++)if(o[i]==1)q.push(i);
	while(q.size())
	{
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].n)
		{
			int v=e[i].v;
			if(vis[v])continue;
			if(u==v)ans+=s[u]>>1,s[u]&=1;
			else x=min(s[u],s[v]),ans+=x;s[u]-=x;s[v]-=x;
			if(--o[v]==1)q.push(v);
		}
		vis[u]=1;
	}
	printf("%d",ans);
	return 0;
}