比赛 2025.9.6 评测结果 RRRRRRRRRRRR
题目名称 Compatible Pairs 最终得分 0
用户昵称 李奇文 运行时间 0.031 s
代码语言 C++ 内存使用 3.71 MiB
提交时间 2025-09-06 11:58:57
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a,b,ans,tot,v[N],hd[N],nxt[N],_n[N],_d[N],ii[N],vis[N];
map<int,int> f;
void add(int x,int y){
	v[++tot]=y;
	nxt[tot]=hd[x];
	hd[x]=tot;
}
void solve(){
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(ii[i]==1) q.push(i);
	}
	while(!q.empty()){
		int x=q.front();
		vis[x]=1;
		q.pop();
		for(int i=hd[x],y;i;i=nxt[i]){
			y=v[i];
			if(!vis[y]){
				if(y==x){
					ans+=(_n[x]>>1);
					_n[x]&=1;
				}else{
					int hs=min(_n[x],_n[y]);
					ans+=hs;
					_n[x]-=ans;
					_n[y]-=ans;
				}
				ii[y]--;
				if(ii[y]==1) q.push(y);
			}
		}
	}
}
int main(){
	//freopen("Compatible.in","r",stdin);
	//freopen("Compatible.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>_n[i]>>_d[i];
		f[_d[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(f.find(a-_d[i])!=f.end()){
			add(i,f[a-_d[i]]);
			ii[f[a-_d[i]]]++;
		}
		if(a!=b&&f.find(b-_d[i])!=f.end()){
			add(i,f[b-_d[i]]);
			ii[f[b-_d[i]]]++;
		}
	}
	solve();
	cout<<ans<<"\n";
	return 0;
}
/*const int N=1e7,inf=0x3f3f3f3f;
int n,a,b,s,t,tot=1,hd[N];
struct node{
	int v,w,nxt;
}e[N];
void add(int x,int y,int z){
	e[++tot].v=y;
	e[tot].w=z;
	e[tot].nxt=hd[x];
	hd[x]=tot;
	e[++tot].v=x;
	e[tot].w=z;
	e[tot].nxt=hd[y];
	hd[y]=tot;
}
int cur[N],d[N];
bool bfs(){
	memset(d,0,sizeof(d));
	queue<int> q;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int f=q.front();
		q.pop();
		for(int i=hd[f];i;i=e[i].nxt){
			int v=e[i].v;
			if(d[v]==0&&e[i].w>0){
				d[v]=d[f]+1;
				q.push(v);
				if(v==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int mf){
	if(u==t) return mf;
	int sum=0;
	for(int i=cur[u];i&&mf;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v;
		if(d[v]==d[u]+1&&e[i].w){
			int f=dfs(v,min(mf,e[i].w));
			if(f==0) d[v]=0;
			e[i].w-=f;
			e[i^1].w+=f;
			sum+=f;
			mf-=f;
			if(mf==0) break;
		}
	}
	if(sum==0) d[u]=0;
	return sum;
}
int Dinic(){
	int flow=0;
	while(bfs()){
		memcpy(cur,hd,sizeof(hd));
		flow+=dfs(s,inf);
	}
	return flow;
}
int _n[N],_f[N],maxn;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>a>>b;
	a+=4,b+=4,s=0,t=1;
	for(int i=1;i<=n;i++){
		cin>>_n[i]>>_f[i];
		_f[i]+=2;
		maxn=max(maxn,_f[i]);
	}
	for(int i=1;i<=n;i++){
		int _a=a-_f[i],_b=b-_f[i];
		if(_a!=_f[i]) add(_f[i],_a+maxn,inf);
		if(_b!=_f[i]) add(_f[i],_b+maxn,inf);
	}
	for(int i=1;i<=n;i++){
		add(s,_f[i],_n[i]);
		add(_f[i]+maxn,t,_n[i]);
	}
	int ans=Dinic()/2;
	for(int i=hd[0];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;	
		if(a-v==v||b-v==v) ans+=(w/2);
	}
	cout<<ans<<"\n";
	return 0;
}*/