Submission #2215376

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inv[201000],fac[201000],mod=1e9+7;
int n,x,y,w1=1999999999,c1,id1,w2=1999999999,c2,id2;
struct xxx{int w,c;}d[201000]; bool used[201000];int cnt[201000],sum=0;
int h[201000],nxt[5001000],K=0,to[5001000];
void ins(int u,int v){nxt[++K]=h[u];h[u]=K;to[K]=v;}
bool cmp(xxx a,xxx b){return a.c<b.c;}
ll ksm(ll k,int p)
{
	ll ans=1ll;while(p){if(p&1)ans=(ans*k)%mod;k=(k*k)%mod;p>>=1;}
	return ans;
}
void init()
{
	fac[0]=inv[0]=1ll;for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%mod;
	inv[n]=ksm(fac[n],mod-2);for(int i=n-1;i>=1;i--)inv[i]=(inv[i+1]*(i+1))%mod;
}
void dfs(int x)
{
	if(used[x])return;cnt[d[x].c]++;used[x]=1;sum++;
	for(int i=h[x];i;i=nxt[i])dfs(to[i]);
}
int main()
{
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;i++)scanf("%d%d",&d[i].c,&d[i].w);
	sort(d+1,d+n+1,cmp);//for(int i=1;i<=n;i++)cout<<d[i].c<<" "<<d[i].w<<endl;
	for(int i=1;i<=n;i++)
	if(d[i].w<=w1){if(d[i].c!=c1)swap(w1,w2),swap(c1,c2),swap(id1,id2);w1=d[i].w;c1=d[i].c;id1=i;}
	else if(d[i].w<=w2&&d[i].c!=c1){w2=d[i].w;c2=d[i].c;id2=i;}
	int k;
	for(int i=1;i<=n;i++)
	{
		int j=i,Min=d[i-1].w;
		while(d[i].c==d[i-1].c){Min=min(Min,d[i].w);i++;}i=j;
		while(d[i].c==d[i-1].c){if(d[i].w+Min<=x)ins(i,k),ins(k,i);i++;}
		k=i;
	}
	for(int i=1;i<=n;i++)if(d[i].c!=c1&&d[i].w+w1<=y)ins(i,id1),ins(id1,i);
	if(c2!=0)for(int i=1;i<=n;i++)if(d[i].c==c1&&d[i].w+w2<=y)ins(i,id2),ins(id2,i);
//	for(int i=1;i<=n;i++,cout<<endl)for(int j=h[i];j;j=nxt[j])cout<<to[j]<<" ";
	dfs(id1);init();ll ans=fac[sum];
	for(int i=1;i<=n;i++)ans=(ans*inv[cnt[i]])%mod;
	printf("%lld",ans);return 0;
}
 //把能互相交换的处理出来，
 //1.同一种颜色：把每种颜色最小的与这种颜色其他球连边 (<=x)
 //2.不同种颜色：取所有球中的最小值（记颜色为c），与它不同颜色的球连边(<=y)，再取一个不同于c颜色的最小值，把它与c颜色的球连边(<=y) 
 //3.计算答案：从2的c开始跑dfs，有被遍历到的球就把它的颜色的出现次数++，设颜色为col的球的出现次数acol，总数为sum，
 //则答案可以看成从sum个位置中选a1个位置填颜色1，再从sum-a1个位置中选a2个位置填颜色2......，则ans=C(sum,a1)*C(sum-a1,a2)*C(sum-a1-a2,a3)...... =sum!/(a1!*a2!......)

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&x,&y);
                          ^
./Main.cpp:30:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%d%d",&d[i].c,&d[i].w);
                                                    ^

Judge Result