Submission #7505891


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;
long long min1 = 2147483647ll,min2 = 2147483647ll;
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]]);
		}
	}
	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 1000
Code Size 2413 Byte
Status
Exec Time 57 ms
Memory 18688 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:80: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:83: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]);
                                                            ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 1000 / 1000 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt
Case Name Status Exec Time Memory
00_example_01.txt 3 ms 8448 KB
00_example_02.txt 3 ms 8448 KB
00_example_03.txt 3 ms 8448 KB
01.txt 3 ms 8448 KB
02.txt 3 ms 8448 KB
03.txt 5 ms 10624 KB
04.txt 3 ms 8448 KB
05.txt 3 ms 8448 KB
06.txt 3 ms 8448 KB
07.txt 27 ms 13696 KB
08.txt 3 ms 8448 KB
09.txt 17 ms 13184 KB
10.txt 11 ms 10880 KB
11.txt 3 ms 8448 KB
12.txt 3 ms 8448 KB
13.txt 5 ms 10624 KB
14.txt 3 ms 8448 KB
15.txt 13 ms 11008 KB
16.txt 26 ms 11648 KB
17.txt 7 ms 10624 KB
18.txt 14 ms 11008 KB
19.txt 24 ms 11520 KB
20.txt 55 ms 14592 KB
21.txt 53 ms 14592 KB
22.txt 51 ms 12544 KB
23.txt 53 ms 16640 KB
24.txt 50 ms 12544 KB
25.txt 54 ms 14592 KB
26.txt 55 ms 16640 KB
27.txt 50 ms 12544 KB
28.txt 57 ms 18688 KB
29.txt 57 ms 16640 KB
30.txt 52 ms 12544 KB
31.txt 57 ms 16640 KB
32.txt 53 ms 12544 KB
33.txt 57 ms 16640 KB
34.txt 53 ms 16640 KB
35.txt 54 ms 16640 KB
36.txt 55 ms 16640 KB
37.txt 53 ms 16640 KB
38.txt 56 ms 16640 KB
39.txt 53 ms 14592 KB
40.txt 51 ms 16640 KB
41.txt 52 ms 14592 KB
42.txt 50 ms 14592 KB
43.txt 48 ms 12544 KB
44.txt 52 ms 16640 KB
45.txt 48 ms 12544 KB
46.txt 52 ms 14592 KB
47.txt 46 ms 12544 KB
48.txt 49 ms 12544 KB
49.txt 47 ms 12544 KB
50.txt 45 ms 14592 KB
51.txt 44 ms 12160 KB
52.txt 44 ms 14592 KB
53.txt 44 ms 14592 KB
54.txt 44 ms 14592 KB