QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125960 | #4968. Aqualin | AH_Lusho# | AC ✓ | 1ms | 3456kb | C++14 | 2.4kb | 2023-07-18 01:40:23 | 2023-07-18 01:40:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int le[30],nu[30],ml[30][30],mn[30][30],n;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int dfs(int x, int y){
int color = ml[x][y];
ml[x][y]=-1;
int c = 1;
queue<pair<int, int> > qn;
qn.push(make_pair(x,y));
while(!qn.empty()){
int nx = qn.front().first, ny = qn.front().second;
qn.pop();
//cout<<nx<<' '<<ny<<endl;
for(int i=0;i<4;i++){
if(nx+dx[i] >=0 and nx+dx[i]<n and ny+dy[i]>=0 and ny+dy[i]<n){
if(ml[nx+dx[i]][ny+dy[i]]==color){
c++;
qn.push(make_pair(nx+dx[i],ny+dy[i]));
ml[nx+dx[i]][ny+dy[i]]=-1;
}
}
}
}
return c;
}
int dfs1(int x, int y){
int color = mn[x][y];
mn[x][y]=-1;
int c = 1;
queue<pair<int, int> > qn;
qn.push(make_pair(x,y));
while(!qn.empty()){
int nx = qn.front().first, ny = qn.front().second;
qn.pop();
//cout<<nx<<' '<<ny<<endl;
for(int i=0;i<4;i++){
if(nx+dx[i] >=0 and nx+dx[i]<n and ny+dy[i]>=0 and ny+dy[i]<n){
if(mn[nx+dx[i]][ny+dy[i]]==color){
c++;
qn.push(make_pair(nx+dx[i],ny+dy[i]));
mn[nx+dx[i]][ny+dy[i]]=-1;
}
}
}
}
return c;
}
int main(){
int a,p=0,p1=0;
char x;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>x>>a;
mn[i][j]=a;
ml[i][j]=((int)x)-65;
}
}
memset(le,0,sizeof(le));
memset(nu,0,sizeof(nu));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(ml[i][j]!=-1){
int k = ml[i][j];
int c = dfs(i,j);
le[k] = max(le[k],c);
//cout<<k<<' '<<le[k]<<endl;
}
}
}
for(int i=0;i<30;i++){
p=p+((le[i]*(le[i]-1))/2);
}
cout<<p<<' ';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mn[i][j]!=-1){
int k = mn[i][j];
int c = dfs1(i,j);
nu[k] = max(nu[k],c);
//cout<<k<<' '<<nu[k]<<endl;
}
}
}
for(int i=0;i<30;i++){
p1=p1+((nu[i]*(nu[i]-1))/2);
}
cout<<p1<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3432kb
input:
5 B 3 A 1 C 1 A 2 A 5 B 4 B 1 B 5 E 4 E 3 C 3 C 2 B 2 D 2 E 2 A 3 C 4 A 4 E 5 D 1 D 3 C 5 D 4 D 5 E 1
output:
21 16
result:
ok single line: '21 16'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
2 A 1 B 1 A 1 B 1
output:
2 6
result:
ok single line: '2 6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
2 Z 1 G 2 B 2 Y 1
output:
0 0
result:
ok single line: '0 0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
26 W 12 J 18 P 4 A 6 A 25 U 11 E 18 O 8 V 8 P 11 K 23 H 24 X 22 N 6 E 23 F 26 S 17 J 3 W 25 J 2 S 7 Y 25 J 16 L 5 P 10 W 6 D 1 Z 1 K 2 N 25 Z 3 X 3 S 11 A 14 I 10 K 20 N 15 A 24 T 5 N 4 L 13 Y 14 K 19 I 5 T 7 I 24 U 7 Y 3 U 15 H 11 L 18 O 2 K 24 F 3 F 10 Q 22 N 18 E 20 K 17 A 7 E 9 Q 12 I 17 S 5 J 6...
output:
25 26
result:
ok single line: '25 26'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
26 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A...
output:
228150 228150
result:
ok single line: '228150 228150'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
26 C 18 J 22 A 5 A 19 A 5 A 5 A 23 A 21 A 6 A 4 A 17 A 6 A 7 A 13 A 18 A 13 A 25 A 23 A 1 A 12 A 14 A 17 A 16 A 9 A 20 A 26 D 17 H 23 A 13 C 22 A 23 C 17 A 4 H 1 A 14 W 22 A 10 N 14 A 8 B 17 O 14 G 4 U 23 X 2 G 8 Z 26 V 24 Q 25 D 2 Y 2 J 9 A 8 U 14 O 7 A 5 O 13 A 16 A 10 A 13 A 4 A 25 A 19 A 14 A 5 ...
output:
72398 31
result:
ok single line: '72398 31'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
26 D 16 C 2 J 1 P 1 O 1 K 1 J 1 V 1 M 1 M 1 V 1 N 1 X 1 V 1 V 1 Q 1 I 1 H 1 A 1 R 1 I 1 N 1 Y 1 E 1 G 1 M 1 N 26 E 25 G 1 M 9 D 1 J 6 E 1 Y 9 F 1 S 26 C 1 A 9 Q 1 L 10 T 22 V 15 E 20 V 14 D 25 A 13 M 20 K 11 E 10 R 15 A 22 T 1 Y 18 V 13 F 1 N 11 H 1 F 1 Y 1 Q 1 Q 1 S 1 X 1 W 1 Q 1 U 1 U 1 T 1 P 1 S ...
output:
27 72779
result:
ok single line: '27 72779'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
26 T 9 T 22 T 21 T 13 T 14 T 16 T 22 T 5 T 11 T 26 T 7 T 8 T 23 T 19 T 14 T 18 T 3 T 2 T 1 T 14 T 22 T 5 T 11 T 3 T 13 T 9 T 16 B 3 T 11 X 3 T 14 V 3 T 26 F 3 T 5 L 3 T 25 G 3 T 20 X 3 T 10 H 3 T 22 V 3 T 13 C 3 T 15 B 3 T 16 R 3 T 25 H 3 T 9 D 3 T 21 G 3 T 10 Z 3 T 6 I 3 T 3 E 3 T 23 I 3 T 1 R 3 T ...
output:
61784 61435
result:
ok single line: '61784 61435'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
20 O 9 O 9 O 4 O 9 O 13 O 10 O 15 O 15 O 20 O 19 O 13 O 4 O 15 O 11 O 18 O 12 O 13 O 14 O 3 O 5 O 20 J 12 O 11 H 12 O 19 H 12 O 18 O 12 O 7 B 12 O 8 N 12 O 19 C 12 O 1 S 12 O 15 M 12 O 7 T 12 O 20 H 12 O 9 P 12 O 9 P 12 O 8 D 12 O 3 S 12 O 14 K 12 O 6 K 12 O 18 P 12 O 10 D 12 O 4 G 12 O 14 Q 12 O 20...
output:
21536 22164
result:
ok single line: '21536 22164'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
25 D 12 U 9 N 12 V 7 P 13 I 4 N 11 A 10 K 24 A 5 C 20 K 3 S 18 M 16 G 23 Q 1 J 21 N 20 Q 2 J 18 D 19 Y 18 V 21 X 14 I 24 P 5 R 8 J 1 O 9 R 2 B 15 F 20 E 3 D 14 C 1 U 21 O 3 R 9 K 18 R 20 J 20 X 13 H 8 H 24 P 3 C 4 S 17 F 9 H 13 D 10 U 20 L 12 D 20 V 16 Y 4 K 23 G 12 B 2 Q 14 S 3 L 1 L 25 J 5 E 14 Q ...
output:
27 33
result:
ok single line: '27 33'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
22 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 A 16 A 17 A 18 A 19 A 20 A 21 A 22 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 11 B 12 B 13 B 14 B 15 B 16 B 17 B 18 B 19 B 20 B 21 B 22 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 C 14 C 15 C 16 C 17 C 18 C 19 C 20 C 21...
output:
5082 5082
result:
ok single line: '5082 5082'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3368kb
input:
26 B 17 G 21 T 18 B 1 Z 13 Y 8 I 7 E 1 S 5 S 22 T 2 U 22 Y 4 P 20 C 24 Q 8 Y 22 S 19 Q 17 X 19 G 16 F 14 J 26 W 11 L 16 S 11 B 17 B 17 B 17 B 17 Z 13 Z 13 I 7 E 1 E 1 S 22 S 22 U 22 U 22 P 20 P 20 Q 8 Q 8 Q 8 Q 17 Q 17 Q 17 F 14 F 14 F 14 L 16 L 16 B 17 B 17 B 17 B 17 Z 13 Z 13 Z 13 E 1 E 1 E 1 S 22...
output:
66499 66110
result:
ok single line: '66499 66110'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
26 T 21 F 6 E 25 G 8 X 23 C 7 B 18 Z 25 T 9 Z 23 X 14 N 22 L 19 Q 21 Y 17 C 24 K 25 L 25 E 8 Z 1 W 9 X 3 A 1 N 14 A 26 I 15 T 21 F 21 E 21 G 21 G 23 C 23 B 23 B 25 B 9 Z 9 X 9 X 22 L 22 L 21 L 17 L 24 K 24 K 25 E 25 Z 25 Z 9 Z 3 A 3 N 3 A 3 A 15 T 21 T 21 T 21 G 21 G 23 G 23 B 23 B 23 B 23 Z 23 X 23...
output:
71168 77581
result:
ok single line: '71168 77581'