Submission #2207651

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MN 200005
#define mod 1000000007
#define inf 0x7fffffff
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
vector<int> b[MN],d[MN];
int fct[MN+5],ivf[MN+5],c[MN],w[MN],mc[MN],num[MN],col[MN];
bool vis[MN];
int n,x,y,cnt,tot,sz,res=1,mn;
inline void dfs(int u){
	vis[u]=1;if (!num[c[u]]) col[++cnt]=c[u];
	++num[c[u]];++tot;int ds=d[u].size();
	for (int i=0;i<ds;++i) if (!vis[d[u][i]]) dfs(d[u][i]);
}
int main()
{
	n=in();x=in();y=in();fct[0]=fct[1]=1;
	ivf[0]=0;ivf[1]=1;w[0]=inf;
	for (int i=1;i<=n;++i){
		c[i]=in(),w[i]=in();
		b[c[i]].push_back(i);
	}
	for (int i=2;i<=MN;++i){
		fct[i]=(1ll*fct[i-1]*i)%mod;
		ivf[i]=(1ll*(mod-mod/i)*ivf[mod%i])%mod;
	}
	for (int i=2;i<=MN;++i) ivf[i]=(1ll*ivf[i-1]*ivf[i])%mod;
	for (int i=1;i<=n;++i){
		mn=0;sz=b[i].size();
		for (int j=0;j<sz;++j) if (w[b[i][j]]<w[mn]) mn=b[i][j];
		if (!mn) continue;mc[i]=mn;
		for (int j=0;j<sz;++j)
		if (mn!=b[i][j]&&w[b[i][j]]+w[mn]<=x)
		d[mn].push_back(b[i][j]),d[b[i][j]].push_back(mn);
	}
	for (int i=n;i>=2;--i) if (w[mc[i]]<w[mc[i-1]]) swap(mc[i],mc[i-1]);
	for (int i=n;i>=3;--i) if (w[mc[i]]<w[mc[i-1]]) swap(mc[i],mc[i-1]);
	for (int j=1;j<=2;++j){
		if (!mc[j]) break;
		for (int i=1;i<=n;++i){
			if (c[i]!=c[mc[j]]&&w[i]+w[mc[j]]<=y)
			d[mc[j]].push_back(i),d[i].push_back(mc[j]);
		}
	}
	for (int i=1;i<=n;++i){
		if (!vis[i]){
			tot=cnt=0;dfs(i);
			res=(1ll*res*fct[tot])%mod;
			for (int j=1;j<=cnt;++j) res=(1ll*res*ivf[num[col[j]]])%mod,num[col[j]]=0;
		}
	}printf("%d",res);return 0;
}

Submission Info

Judge Result