Submission #2367701

---

Source Code Expand

#include<cstdio>
#define ll long long
const int N=2e5+5,mo=1e9+7;
int n,nx,ny,mx1,mx2,a[N],b[N],mx[N],inv[N],i;
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
int Min(int x,int y){return b[x]<b[y]?x:y;}
int et,he[N];
struct edge{int l,to;}e[4*N];
void line(int x,int y){
	e[++et].l=he[x];he[x]=et;e[et].to=y;
	e[++et].l=he[y];he[y]=et;e[et].to=x;
}
int cnt,qn,q[N],g[N],ans;
void dfs(int x){
	cnt++;ans=(ll)ans*cnt%mo;
	if (!(g[a[x]]++)) q[++qn]=a[x];
	a[x]=0;
	for (int i=he[x];i;i=e[i].l)
		if (a[e[i].to]) dfs(e[i].to);
}
int main(){
	n=read();nx=read();ny=read();b[0]=1e9+1;
	for (i=1;i<=n;i++){
		a[i]=read();b[i]=read();
		mx[a[i]]=Min(mx[a[i]],i);
	}
	for (i=1;i<=n;i++)
		if (b[mx[i]]<b[mx1]) mx2=mx1,mx1=mx[i];
		else if (b[mx[i]]<b[mx2]) mx2=mx[i];
	for (i=1;i<=n;i++){
		if (i!=mx[i]&&b[i]+b[mx[a[i]]]<=nx) line(i,mx[a[i]]);
		if (a[i]==a[mx1]){
			if (b[i]+b[mx2]<=ny) line(i,mx2);
		}
		else if (b[i]+b[mx1]<=ny) line(i,mx1);
	}
	for (inv[1]=1,i=2;i<=n;i++)
		inv[i]=(ll)inv[mo%i]*(mo-mo/i)%mo;
	for (i=2;i<=n;i++) inv[i]=(ll)inv[i]*inv[i-1]%mo;
	for (ans=1,i=1;i<=n;i++) if (a[i]){
		qn=0;cnt=0;dfs(i);
		for (i=1;i<=qn;i++)
			ans=(ll)ans*inv[g[q[i]]]%mo,g[q[i]]=0;
	}
	printf("%d",ans);
}

Submission Info

Judge Result