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