QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139409 | #4968. Aqualin | artcs | AC ✓ | 1ms | 3564kb | C++17 | 2.8kb | 2023-08-13 12:38:01 | 2023-08-13 12:38:02 |
Judging History
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'