QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125960#4968. AqualinAH_Lusho#AC ✓1ms3456kbC++142.4kb2023-07-18 01:40:232023-07-18 01:40:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 01:40:26]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3456kb
  • [2023-07-18 01:40:23]
  • 提交

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'