QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#59166#1836. Glory GraphtricyzhkxAC ✓2817ms13468kbC++14765b2022-10-28 13:38:562022-10-28 13:38:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-28 13:38:58]
  • 评测
  • 测评结果:AC
  • 用时:2817ms
  • 内存:13468kb
  • [2022-10-28 13:38:56]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[4010][4010];
bitset<4001> G[4010];
ll C2(ll n){return n*(n-1)/2;}
ll C3(ll n){return n*(n-1)*(n-2)/6;}
int main()
{
	int n,m=0;
	ll ans=0;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(s[i][j]=='Y') G[i][j]=1,m++;
	m/=2;ans=2*C2(m)-m*C2(n-2);
	for(int i=1;i<=n;i++) ans+=2*C2(G[i].count())*(n-4)-3*C3(G[i].count());
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)if(G[i][j])
			ans-=(G[i]&G[j]).count()*(n-3);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)if(G[i][j])
		{
			int t=(G[i]&G[j]).count();
			ans+=t*(G[i].count()-2)-(G[i].count()-1)*(G[j].count()-1)+t;
		}
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 5788kb

input:

5
-YBYB
Y-BBB
BB-BY
YBB-Y
BBYY-

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 3ms
memory: 5584kb

input:

6
-YYYYY
Y-YYBB
YY-YYY
YYY-YB
YBYY-Y
YBYBY-

output:

-6

result:

ok 1 number(s): "-6"

Test #3:

score: 0
Accepted
time: 3ms
memory: 5640kb

input:

5
-YBYY
Y-YYY
BY-YB
YYY-Y
YYBY-

output:

-2

result:

ok 1 number(s): "-2"

Test #4:

score: 0
Accepted
time: 3ms
memory: 5784kb

input:

5
-YBYY
Y-YYY
BY-BY
YYB-Y
YYYY-

output:

-2

result:

ok 1 number(s): "-2"

Test #5:

score: 0
Accepted
time: 2ms
memory: 5704kb

input:

6
-YYYBY
Y-YBBY
YY-BBY
YBB-BB
BBBB-B
YYYBB-

output:

-3

result:

ok 1 number(s): "-3"

Test #6:

score: 0
Accepted
time: 2ms
memory: 5704kb

input:

6
-YYBYB
Y-BBYY
YB-BBB
BBB-YB
YYBY-Y
BYBBY-

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 2ms
memory: 5792kb

input:

10
-YBBYBBBBB
Y-BYBYYYYB
BB-YBYBYYY
BYY-BBYBBB
YBBB-YYYYB
BYYBY-YBBB
BYBYYY-YYY
BYYBYBY-YY
BYYBYBYY-B
BBYBBBYYB-

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 3ms
memory: 5660kb

input:

40
-YYYYBBBBYYBYBBBBBBBBYYBBBBYYYYBBYYBBBYB
Y-YYYBBYBYBYYYBBBYBYBBYBYYBYYYBBYBBYBYYB
YY-YBYBBBYYYYYYBYBYYYBBBBYYBBBBYBYBBYYYY
YYY-BYBBYBYYBYBBBYYBYBBBBBYBYBYBBYYBBBBY
YYBB-BBBYYBYBYYYYYBYBBBYYBBBBYBYBBYYBBYB
BBYYB-BBYYBYYBBBYBYBBYYBYYYBBYBYBBYYBYYY
BBBBBB-YBYBBBBYBBYYYBBBBBBYYYBYYBBBYBYYY
BYBBBBY-YY...

output:

458

result:

ok 1 number(s): "458"

Test #9:

score: 0
Accepted
time: 3ms
memory: 5800kb

input:

40
-YYYYYYYYYYYYYYBYYYYYBBYYYYYYYYBYYYYYYBB
Y-BBYYYBYYYYYYYYYYYYYYYYBYYBYYYBYBBYYYYY
YB-YBYYYYYYYYYYYYBYYYYYYYYBYYBYYYYBYBYBY
YBY-YYBYYYYYYBYYYBBYBYYYYYYYYYYYYYYYYBYY
YYBY-YYYYYYYYYYYYYYYYYYYBYBYYYYYYYYYYYYY
YYYYY-BYYYYYYYYYYYYYYYYYYYYBBYBYYYYYYYYY
YYYBYB-BYYBYYYYYBYYYYBYYBYYYYYYYYYYYYBYY
YBYYYYB-YY...

output:

-34287

result:

ok 1 number(s): "-34287"

Test #10:

score: 0
Accepted
time: 3ms
memory: 5704kb

input:

40
-YYYBBBBYBYYYBYYYYYYBYYYBYBYBYYYBYBYYBBY
Y-BYYYYBYYYBYBYBBBBBYYBYBYYYBYYYBYBBYBYY
YB-YYYYBBBYBYYBBYYYBYBYYBYYBYBYYBBYYYYBB
YYY-YYYYYBYYYYBYYYBBYYYBBYYBYYYYBYYYYBYY
BYYY-BYBBYBYYBBBBBBBYYBYBYYBYBBBYYYYBBYB
BYYYB-BBYBBYYYYYBYBBYBBYBBBBYBYBYYYYBYBB
BYYYYB-BYYYBYYYBBYBBYBYYBYBBBBBYYBBYYBBY
BBBYBBB-YY...

output:

-8539

result:

ok 1 number(s): "-8539"

Test #11:

score: 0
Accepted
time: 6ms
memory: 5756kb

input:

100
-YYBYBBYBYBYYYBBYBYYYYYBYBBYBBYBYYBYBYYBYYBYYYBBYBYBBBYBBYYBBYYBBBYYBYBBYYYBBYBBYBBBYBBBYBBYBYBBBBYY
Y-YYYYBBBBYYBYYBYYYBYYYBYYYBYBBBYYBBBBYYYBYYBBYBYYBYBYBYBBBYYYBYYYYYBBYBBYBBBYYBBYBBYYYYYBYBBYBYYYBB
YY-BYBBBYBYBYYBBBBBYBBYBBBYBYYYBYYYYYBYBBBBYBYYBBYBBBYYBYBBBBYYBYBYBYBYBYYYYBBYYYYBYYBYYYBYYBY...

output:

5474

result:

ok 1 number(s): "5474"

Test #12:

score: 0
Accepted
time: 5ms
memory: 5612kb

input:

100
-BBBBBBBBBBBBBBBBBYBYBBBBYBYYBYBYBBBBBYBBBBBBBBYBBBYBBYBBBYYBBBYBBBBYBBBYYBBBBYYYBBBBBYYBYBYBBBYBYYY
B-BBBBYYBBYYYBBYBBBBYYBBBYBYBBBBBBBYBBBYBYBBBBBBBBBYBYYBBBBYBYYBBBYYBYBBYBBYYBYBBBBBBYBBYYBYBBBBBBBY
BB-BBYBBYYBBBBBBBBBBYYYBBBYBBBYBBBYBYYBBYBYYBBBBBYBYYYYYBBBBYYYYBYBYBBBBYBYBBBBBYYBBYYBYBBYBBB...

output:

-649105

result:

ok 1 number(s): "-649105"

Test #13:

score: 0
Accepted
time: 429ms
memory: 8224kb

input:

1000
-BBYBYBBYYYYBBYBBBBYBYYBYBYYBBYBBYYBYBYBBYBYBYBYBYYYYYBYBBBBBBBBBBYYBBBBYBBYBBYYYYYBBBYBYBBYYBYYBBYYYYYBBYBYBYBBYBYBYYYYBBBBYBYYYYYBYYYYBYBYYYBYBYYYYBBYBYBYBYBBBYYBYBBBBBBBBYYYYBYBYYBYBYBYYBBBYBYYYBBYBBYYYYYBBYBBYYYYYBYYBYYYBBBYYYYBBBBBYYBBBYYYBYYBYYBYBYYBBYYBBBYBYBYYBBBBYYBYYYBBBYYBBBBYBBBYYYB...

output:

-3233119

result:

ok 1 number(s): "-3233119"

Test #14:

score: 0
Accepted
time: 307ms
memory: 8932kb

input:

1000
-BBYBBBBBYBBBYYBBBYYBYBBBYBYBBBYBBYBBYBBYBBBYYBBYBYYBBBBBYYBBBBBYYYBBBBBBYBBBYYYBBBYBYYYBBBBBYBYYYBBBBBYYBBBBYYBBBBBBBBBBBBBYBBBBYBBBBYBBBBYBYYBBBBBYBYYBBBYBYBBBBBYYBBBBBBBBBBBBBBBYYBBYYYYBBYBYYBBBBBBYBBYBBBYBBBBYBYYBBBBBYYBYBBYBBBBBYBYYBBYBBYYBYBYYYYYYBBYYBBBBYBYBBYBBBYYBYYBBBYBBYBBYBYBBBBBYBB...

output:

-6052668374

result:

ok 1 number(s): "-6052668374"

Test #15:

score: 0
Accepted
time: 721ms
memory: 9600kb

input:

1000
-BYYBYYYYYYYYYBYYYYYYYYYYYYBYYYYBYYYYYBYYBYYYYYYYYYYYYYYYYBYYYYBYYYYYYYYYBYYYBBYYYYYYYYYYYYYYYYYYYYYYYYYYYYBYYYYYBYBYYYBYYBYYYYBBYYYYYYYYYYYYYYYYYYBYYYBYBYYBYYBYYBYBYYBYBYYYYYYYYYYYYYYBBBYYBYYYYYBYYBYYYYYYYYYBYBYYYYYYYYYYYYBYYYYYYYYYYYYYYYYYYYYBYYYYYYYYYBYYYBYYYYYYBYYBYYYYYBYYYYYBYYYYBBYBYYBYBY...

output:

-15355158378

result:

ok 1 number(s): "-15355158378"

Test #16:

score: 0
Accepted
time: 1799ms
memory: 13308kb

input:

2000
-BYBBYYBYBYBYBBYBBBYBBYYBYBYYYYYYBBYBBBYBYBBYYBBBYBBBYBBBYBYYBYBYYYYYYBYYYBYBBBBBBYYBYYBYYYYYYYBBBYYYBYYBBBYBYBBBBBYBBYBYBYYBYBYYBBYBYBBYYBYBBBBBBBBBBBYYBBBBBYBYYYBYYBYYYBYYYYYBYYYYBBBBBBBYYYYBYYBBBYBYBBYYYYBBYBYBYBBBYBBBBYBBYBYYBYYYBBYBBYYYBYBYYYBYYYYBYBYBBBBBBBYYBBYYYBBYBBBBBYBBBYYYYYBYBBBYYY...

output:

14871328

result:

ok 1 number(s): "14871328"

Test #17:

score: 0
Accepted
time: 1170ms
memory: 13464kb

input:

2000
-BBBBYYBBYYYBYBBYBBYBBBBBYBBBBBBYBYYYBBBBBBBBBBBBBYBYBBBBBBBBBBBYYBBBBBBBBBBBYYBBBBYBBBYYBBBBBYBBBBBYBBBBBBYBYBBYYYBYBBBBYYBBBYYYBYBBYBBBBBYBBBBBBBBYBBYBBYBBBBYBBBYBBBBYYYBBYBYBBBBBYBYBYYBBYYBBBBBBBBBBYYYYBYBBYBYBBBBBBBBYBYBYBBBBBBYYYBYBBBBBBBBYYBBBBBBBYYBBBYYBYBBBBYBBYYBBBBYBBBBBYBBYYBBYBBBYBY...

output:

-98751748805

result:

ok 1 number(s): "-98751748805"

Test #18:

score: 0
Accepted
time: 2817ms
memory: 13468kb

input:

2000
-YYYYBYYYYYYYYYYBYYYYYBYYYYYBBBYYYYYYYBYYYYYYYYBBYYYYYYYYYBYYYYYBYBYYYYYYYYBYYYBYYYYYYYBYYYYYYYYYYYYYYBBBBBYYYYYYYYYYYYYYYBYYYYBYYYYYBYBYYYYYYYYYYBYYYYBYYYYYYYBYYYYYYYYYYBYYYYYYBBYYBYYBBYYYYYBYYBYYYYYYYBYBYYBYYBYBBYYYYYBYBYYBYYYYYYYBYYBYYYYYYYYYBYBYYBYYYYYYYYYYYYYYBYBYYYYYBYYYYYYYBYBYYYYYBYYYYY...

output:

-246238368355

result:

ok 1 number(s): "-246238368355"

Test #19:

score: 0
Accepted
time: 907ms
memory: 12556kb

input:

2000
-BBBBYBBBBBBYBYBBBYYBBBBBBBBBBBBBBBBYBBBYBYYBBBBBBBBBYYBBBYBBBBBYBBYBBBBBYBBBYBBBBBBBBBBBBBBBBBBBYBBBYYBYBBYBYBBYYBYYBBYBYYYYBBYBYBBBBBYYBBYYBBBBBYBBBBBBYBBBBYBBBYBBBBYBBBBBBBBBBBBBBYBBBBBYBYYBBBBYBBBYBBYBBBBBBYBBBBBYYYBBYYBBBBBBBBBBBBYYBBBBYBYBBBBYYBBBYBBBBBBBBBBYBBBBBBBBYBYYYBBYBYYBBBBBYBBBBB...

output:

-186887776300

result:

ok 1 number(s): "-186887776300"

Test #20:

score: 0
Accepted
time: 451ms
memory: 13324kb

input:

2000
-BBYYBBBBBBBBBBBBYBYBBBBBBBBBBBBBBYBBBBBBBBBBBBYBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBYBBYBBBBBBBBBBBBBBBBBBBBBBBBBBBYBBBBBBBBBBBYBBBBBYBBYBBBBBYYBBYBYBYBBBYBBBBYBBBBYBBBBBBBBBBBBBYBBBBBBBBBBBBBBYBBBBBBBBBBBBBBBBYBBBYBBBYBBBBBBBYBBYBBBBBBBBBBYBBYBBBBYBBYYBBBBBBYBBBBBBBBBYBBBBBBBBBBBBBBBBBYYBBYBBYBBYBB...

output:

-245343471492

result:

ok 1 number(s): "-245343471492"

Test #21:

score: 0
Accepted
time: 1344ms
memory: 12596kb

input:

2000
-YYBBBBBBBBBBBBBBBYYBBBBYBBBYYBYBBYYBYYYYBBYBYYBBBYYYBBBYBBYBYYBBBBYBBYBBBBBYBYBYYYBBYBYBBBBYYBBBBBBYYBBBBYBBYYBBBBYBYBBBBYBBYBBYYYBYYBBYBBYBYYBBYBBYBYYYBBBBBBBYYBBYBBBBYBBYYBYYYBYBYBBYYYBBBBBBBBBYYBBBBBYBBBBYBBBBBYBBYYYBBBYBBYYBBBYYBBYBBBBBBYBBYBYBBBBBBBYBBBYBBBBBYBBYBYYBBBYYBBBBBBBBYBYBBYBYBY...

output:

-50383073264

result:

ok 1 number(s): "-50383073264"