Submission #2207396

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define MN 200005
#define ll long long
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll fac[MN],inv[MN];
int n,x,y,cnt=0,c[MN],w[MN],ge[MN];bool vis[MN];
vector<pair<int, int> >r[MN];
vector<pair<int, int> >p;
vector<int> v[MN],tmp;
void dfs(int u){
    vis[u]=1;
    ++cnt,++ge[c[u]],tmp.push_back(c[u]);
    for(int i=0;i<v[u].size();i++)
        if(!vis[v[u][i]]) dfs(v[u][i]);
}
int main(){
	n=read(),x=read(),y=read();
	fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(ll i=2;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%mod;
    for(int i=1;i<=n;i++) c[i]=read(),w[i]=read(),r[c[i]].push_back(make_pair(w[i],i));
    for(int i=1;i<=n;i++)if(r[i].size()){
    	sort(r[i].begin(),r[i].end());p.push_back(r[i][0]);
    	for(int j=1;j<r[i].size();j++)
    		if(r[i][j].first+r[i][0].first<=x)
    			v[r[i][0].second].push_back(r[i][j].second),
    			v[r[i][j].second].push_back(r[i][0].second);
	}
    sort(p.begin(),p.end());
    int id=p[0].second;
    for(int i=1;i<=n;i++){
    	if(c[i]==c[id]||w[i]+w[id]>y) continue;
    	v[id].push_back(i),v[i].push_back(id);
	}
    if(p.size()>1){
    	id=p[1].second;int cmin=c[p[0].second];
    	for(int i=0;i<r[cmin].size();i++)
    		if(r[cmin][i].first+w[id]<=y)
			v[r[cmin][i].second].push_back(id),v[id].push_back(r[cmin][i].second);
	}
	dfs(p[0].second);
    ll ans=fac[cnt];
    for(int i=0;i<tmp.size();i++)
        ans=(ans*inv[ge[tmp[i]]])%mod,ge[tmp[i]]=0;
    printf("%lld\n",ans);
    return 0;
}

Submission Info

Judge Result