Submission #7505876


Source Code Expand

Copy
#include <bits/stdc++.h>
#define mod 1000000007ll
#define M 200010
using namespace std;
struct edge
{
	int to;
	int nxt;
}e[3000010];
int n,minnum,minnum2;
int color[M],dlfl[M],pos[M],vis[M];
long long val[M],minn[M];
long long fac[M],rfac[M];
long long X,Y;
int head[M],cnt;
void addedge(int x,int y)
{
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void add(int x,int y)
{
	addedge(x,y);
	addedge(y,x);
}
long long qpow(long long a,long long b)
{
	long long ans = 1,res = a;
	while(b)
	{
		if(b&1)ans = (ans * res) % mod;
		res *= res;
		res %= mod;
		b >>= 1;
	}
	return ans;
}
long long C(long long n,long long k)
{
	return  fac[n] * rfac[k] % mod * rfac[n - k] % mod;
}
void init()
{
	fac[0] = 1;
	for(int i = 1;i <= n;i++)fac[i] = (i * fac[i - 1]) % mod;
	rfac[n] = qpow(fac[n],mod - 2);
	for(int i = n; i > 0; i--)rfac[i - 1] = (i * rfac[i]) % mod;
}
void dfs(int x)
{
	vis[x] = 1;
	for(int i = head[x]; i; i = e[i].nxt)
	{
		if(!vis[e[i].to])dfs(e[i].to);
	}
}
void find()
{
	for(int i = 1; i <= n; i++)
	{
		if(val[i] < min1)
		{
			min1 = val[i];
			minnum = i;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(val[i] <= min2 && color[i] != color[minnum])
		{
			min2 = val[i];
			minnum2 = i;
		}
	}
}
int main()
{
	scanf("%d%lld%lld",&n,&X,&Y);
	init();
	for(int i = 1;i <= n;i++)minn[i] = 2147483647ll;
	for(int i = 1;i <= n;i++)scanf("%d%lld",&color[i],&val[i]);
	for(int i = 1;i <= n;i++)
	{
		if(val[i] < minn[color[i]])
		{
			minn[color[i]] = val[i];
			pos[color[i]] = i;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(i != pos[color[i]] && val[i] + minn[color[i]] <= X)
		{
			add(i,pos[color[i]]);
		}
	}
	long long min1 = 2147483647ll,min2 = 2147483647ll;
	find();
	for(int i = 1; i <= n; i++)
	{
		if(i != minnum)
		{
			if(color[i] != color[minnum] && val[i] + val[minnum] <= Y)
			{
				add(i,minnum);
			}
			if(minnum2 && color[i] != color[minnum2] && val[i] + val[minnum2] <= Y)
			{
				add(i,minnum2);
			}
		}
		
	}
	dfs(minnum);
	long long fldl = 0;
	for(int i = 1; i <= n; i++)
	{
		if(vis[i])
		{
			dlfl[color[i]]++;
		}
	}
	for(int i = 1;i <= n;i++)fldl += dlfl[i];
	long long ans = 1;
	for(int i = 1; i <= n; i++)
	{
		if(dlfl[i])
		{
			ans *= C(fldl,dlfl[i]);
			ans %= mod;
			fldl -= dlfl[i];
		}
	}
	printf("%lld",ans);
	return 0;
}

Submission Info

Submission Time
Task D - Colorful Balls
User luogu_bot5
Language C++ (GCC 5.4.1)
Score 0
Code Size 2414 Byte
Status

Compile Error

./Main.cpp: In function ‘void find()’:
./Main.cpp:62:15: error: ‘min1’ was not declared in this scope
   if(val[i] < min1)
               ^
./Main.cpp:70:16: error: ‘min2’ was not declared in this scope
   if(val[i] <= min2 && color[i] != color[minnum])
                ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:79:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld",&n,&X,&Y);
                              ^
./Main.cpp:82:60: 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%lld",&color[i],&val[i]);
                                                            ^