比赛 |
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;
}