QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139409#4968. AqualinartcsAC ✓1ms3564kbC++172.8kb2023-08-13 12:38:012023-08-13 12:38:02

Judging History

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

  • [2023-08-13 12:38:02]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3564kb
  • [2023-08-13 12:38:01]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

int n;

string cad;
int M1[26][26],M2[26][26], index1, index2;
map<string, int> MAP1, MAP2;
int scc1[26], scc2[26];
bool F1[26][26], F2[26][26];
int dx[4] = {0,1,0,-1}; 
int dy[4] = {1,0,-1,0};

int dfs1(int id_i, int id_j, int conn)
{
    if(M1[id_i][id_j]!=conn)
        return 0;
    if(id_i<0 || id_j<0 || id_i==n||id_j==n)
        return 0;
    if(F1[id_i][id_j])
        return 0;

    F1[id_i][id_j] = true;

    int scc = 1;
    for(int i=0;i<4;i++)
    {
        scc += dfs1(id_i+dx[i], id_j+dy[i], conn);
    }
    return scc;
}


int dfs2(int id_i, int id_j, int conn)
{
    if(M2[id_i][id_j]!=conn)
        return 0;
    if(id_i<0 || id_j<0 || id_i==n||id_j==n)
        return 0;
    if(F2[id_i][id_j])
        return 0;

    F2[id_i][ id_j] = true;

    int scc = 1;
    for(int i=0;i<4;i++)
    {
        scc += dfs2(id_i+dx[i], id_j+dy[i], conn);
    }
    return scc;
}



int main()
{
    cin>>n;


    memset(scc1, 0, sizeof scc1);
    memset(scc2, 0, sizeof scc2);
    index1=0, index2=0;

    for (int i=0; i<n; i++)
    {
        for(int j=0; j<2*n; j++)
        {
            cin>>cad;
            if(j%2==0)
            {
                if(MAP1.count(cad)==0)
                    MAP1[cad] = index1++;
                M1[i][j/2] = MAP1[cad];
                //cout<<MAP1[cad]<<" ";
            }
            else
            {
                if(MAP2.count(cad)==0)
                    MAP2[cad] = index2++;
                M2[i][j/2] = MAP2[cad];
                //cout<<MAP2[cad]<<" ";
            }
        }
    }


//    for(int i=0; i<n;i++)
//    {
//        for(int j=0; j<n;j++)
//            cout<<M1[i][j]<<" ";
//        cout<<endl;
//    }
//
//    for(int i=0; i<n;i++)
//    {
//        for(int j=0; j<n;j++)
//            cout<<M2[i][j]<<" ";
//        cout<<endl;
//    }
//

    memset(F1, false, sizeof F1);
    memset(F2, false, sizeof F2);
    int val1=0, val2=0;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(F1[i][j] == false)
            {
                val1 = dfs1(i,j, M1[i][j]);                
                scc1[M1[i][j]] = max(scc1[M1[i][j]],val1);
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(F2[i][j] == false)
            {
                val2 = dfs2(i,j, M2[i][j]);                
                scc2[M2[i][j]] = max(scc2[M2[i][j]],val2);
            }
        }
    }

    int s1=0, s2 =0;

    for(int i=0;i<26;i++)
    {
        s1= s1+(scc1[i]*(scc1[i]-1))/2;
        s2= s2+(scc2[i]*(scc2[i]-1))/2;
    }

    cout<<s1<<" "<<s2<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3520kb

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: 3448kb

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: 3492kb

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: 0ms
memory: 3532kb

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: 3540kb

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: 1ms
memory: 3496kb

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: 3516kb

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: 3516kb

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: 3496kb

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: 3564kb

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: 3464kb

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: 1ms
memory: 3504kb

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: 1ms
memory: 3468kb

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'