Submission #2203833
Source Code Expand
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)
using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;
const int M=1000000007;
int n,X,Y,Ans=1;
int c[200001],w[200001]={INF};
int minw[200001];
bool cmp(int p1,int p2){return w[p1]<w[p2];}
int colors[200001],h[200001],nxt[1000001],to[1000001],tot;
void ins(int*arr,int x,int y){nxt[++tot]=arr[x];to[tot]=y;arr[x]=tot;}
void insw(int x,int y){ins(h,x,y);ins(h,y,x);}
int frc[200001]={0,1},inv[200001]={0,1};
int vis[200001],cnt[200001],stk[200001],tyq,cnts;
void DFS(int u){
vis[u]=1; if(!cnt[c[u]]) stk[++tyq]=c[u]; ++cnt[c[u]]; ++cnts;
for(int i=h[u];i;i=nxt[i]){
if(!vis[to[i]]) DFS(to[i]);
}
}
int main(){
scanf("%d%d%d",&n,&X,&Y);
F(i,1,n) scanf("%d%d",c+i,w+i);
F(i,2,200000) frc[i]=(ll)frc[i-1]*i%M;
F(i,2,200000) inv[i]=(ll)(M-M/i)*inv[M%i]%M;
F(i,2,200000) inv[i]=(ll)inv[i-1]*inv[i]%M;
F(i,1,n) ins(colors,c[i],i);
F(i,1,n){
int mini=0;
for(int j=colors[i];j;j=nxt[j])
if(w[to[j]]<w[mini]) mini=to[j];
if(!mini) continue;
minw[i]=mini;
for(int j=colors[i];j;j=nxt[j])
if(to[j]!=mini&&w[to[j]]+w[mini]<=X) insw(mini,to[j]);
}
sort(minw+1,minw+n+1,cmp);
F(k,1,2){
if(!minw[k]) break;
F(i,1,n){
if(c[i]!=c[minw[k]]&&w[i]+w[minw[k]]<=Y)
insw(minw[k],i);
}
}
F(i,1,n){
if(!vis[i]){
tyq=cnts=0;
DFS(i);
Ans=(ll)Ans*frc[cnts]%M;
F(j,1,tyq) Ans=(ll)Ans*inv[cnt[stk[j]]]%M, cnt[stk[j]]=0;
}
}
printf("%d",Ans);
return 0;
}
Submission Info
Submission Time
2018-03-14 17:43:19+0900
Task
D - Colorful Balls
User
vjudge2
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1737 Byte
Status
TLE
Exec Time
2103 ms
Memory
16000 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32: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:33:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
F(i,1,n) scanf("%d%d",c+i,w+i);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1000
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All
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
AC
8 ms
9984 KB
00_example_02.txt
AC
7 ms
7936 KB
00_example_03.txt
AC
8 ms
9984 KB
01.txt
AC
8 ms
9984 KB
02.txt
AC
8 ms
9984 KB
03.txt
AC
10 ms
9984 KB
04.txt
AC
8 ms
9984 KB
05.txt
AC
8 ms
9984 KB
06.txt
AC
8 ms
9984 KB
07.txt
AC
36 ms
14720 KB
08.txt
AC
8 ms
9984 KB
09.txt
AC
23 ms
14336 KB
10.txt
AC
17 ms
14208 KB
11.txt
AC
8 ms
9984 KB
12.txt
AC
8 ms
9984 KB
13.txt
AC
10 ms
10112 KB
14.txt
AC
8 ms
9984 KB
15.txt
AC
21 ms
14336 KB
16.txt
AC
35 ms
14720 KB
17.txt
AC
12 ms
12160 KB
18.txt
AC
20 ms
14336 KB
19.txt
AC
33 ms
14592 KB
20.txt
AC
75 ms
15616 KB
21.txt
AC
73 ms
15616 KB
22.txt
AC
72 ms
15488 KB
23.txt
AC
75 ms
15872 KB
24.txt
AC
71 ms
15488 KB
25.txt
AC
75 ms
15616 KB
26.txt
AC
75 ms
15872 KB
27.txt
AC
74 ms
15360 KB
28.txt
TLE
2103 ms
16000 KB
29.txt
AC
76 ms
15744 KB
30.txt
AC
72 ms
15488 KB
31.txt
AC
76 ms
15872 KB
32.txt
AC
74 ms
15488 KB
33.txt
AC
76 ms
15872 KB
34.txt
AC
71 ms
15744 KB
35.txt
AC
64 ms
15360 KB
36.txt
AC
69 ms
15488 KB
37.txt
AC
64 ms
15360 KB
38.txt
AC
64 ms
15360 KB
39.txt
AC
64 ms
15360 KB
40.txt
AC
70 ms
15872 KB
41.txt
AC
72 ms
15744 KB
42.txt
AC
71 ms
15744 KB
43.txt
AC
70 ms
15488 KB
44.txt
AC
71 ms
15872 KB
45.txt
AC
70 ms
15488 KB
46.txt
AC
73 ms
15616 KB
47.txt
AC
53 ms
15360 KB
48.txt
AC
55 ms
15360 KB
49.txt
AC
54 ms
15360 KB
50.txt
AC
59 ms
15488 KB
51.txt
AC
60 ms
15360 KB
52.txt
AC
51 ms
15360 KB
53.txt
AC
51 ms
15360 KB
54.txt
AC
51 ms
15360 KB