QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62109#2827. Autobiographydefathom#TL 203ms12124kbC++141.0kb2022-11-17 14:27:442022-11-17 14:27:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 14:27:45]
  • 评测
  • 测评结果:TL
  • 用时:203ms
  • 内存:12124kb
  • [2022-11-17 14:27:44]
  • 提交

answer

#include<bits/stdc++.h>
const int N=1e6+5;
//const ll mod=998244373;
using namespace std;

int n,t;
int m;
string s;
//int x,y;
int ans;
int head[N],cnt;
int vis[N];

struct edge{
   	int next;
   	int to;
}e[N];

void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}

void dfs(int x,int num)
{
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next)
	  {
	  	int y=e[i].to;
	  	if(vis[y])
	  	  continue;
	  	if(num==3&&s[y]=='o')
	  	  {
	  	  	++ans;
	  	  	continue;
	  	  }
	    if(num==2&&s[y]=='b')
	      	dfs(y,3);
	    if(num==1&&s[y]=='o')
	      dfs(y,2);
	  }
	vis[x]=0;
}

int main()
{
	while(cin>>n>>m)
	  {
	    cin>>s;
	    s=" "+s;
	    cnt=0;
	    for(int i=1;i<=n;++i)
	      head[i]=0;
	    ans=0;
	    while(m--)
	      {
	      	int x,y;
	      	cin>>x>>y;
	      	add(x,y);
	      	add(y,x);
	      }
	    for(int i=1;i<=n;++i)
	      {
	      	if(s[i]=='b')
	      	  dfs(i,1);
	      }
	    printf("%d\n",ans);
     }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7548kb

input:

5 4
bbobo
1 3
2 3
3 4
4 5
4 6
bobo
1 2
1 3
1 4
2 3
2 4
3 4
4 0
bobo

output:

2
4
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 203ms
memory: 7600kb

input:

4 4
oobo
2 3
4 1
4 3
3 1
4 3
obob
1 4
2 3
1 2
4 4
obob
3 1
2 3
2 1
1 4
4 3
bboo
2 4
4 1
3 4
4 3
bbbo
1 4
1 3
4 2
4 4
obbo
3 4
2 4
2 3
3 1
4 3
bobo
2 3
4 3
1 4
4 3
obbb
3 4
4 2
1 4
4 5
bobo
4 1
2 1
3 1
4 3
2 4
4 4
obbo
3 4
3 1
2 3
1 4
4 3
bobb
4 2
4 1
2 3
4 3
obbo
3 1
3 2
1 2
4 4
ooob
2 1
3 1
3 4
1 4...

output:

0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
4
1
0
0
0
0
4
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result:

ok 50000 lines

Test #3:

score: 0
Accepted
time: 88ms
memory: 7600kb

input:

8 13
bbooboob
8 3
8 4
1 3
1 8
4 2
2 6
4 5
1 5
6 4
7 1
2 3
2 7
5 8
5 8
bbbob
3 1
2 4
1 4
1 2
2 5
4 3
4 5
5 1
13 16
ooboooobboobb
5 4
9 6
9 13
9 2
11 4
11 9
5 7
1 9
2 5
12 3
2 8
8 11
10 11
4 9
11 12
4 13
20 17
bbbobobobooobooobooo
13 9
16 9
10 17
6 8
4 9
1 4
3 19
7 17
2 18
17 9
18 8
14 19
6 11
9 15
4 ...

output:

22
0
19
8
6
6
0
12
27
4
37
3
3
0
45
4
4
8
3
4
4
4
5
2
4
3
0
4
8
5
6
5
6
11
3
8
8
8
0
3
3
13
0
4
18
11
0
3
4
1
0
8
14
10
6
9
4
9
12
5
4
4
0
3
2
0
8
0
6
0
2
0
28
2
2
16
2
18
10
2
4
6
4
8
14
0
10
2
2
8
10
0
11
5
1
26
12
8
0
0
0
19
16
28
0
10
1
2
1
30
8
2
28
1
4
3
20
6
0
0
3
19
3
0
0
6
12
4
15
0
9
4
12
...

result:

ok 10000 lines

Test #4:

score: 0
Accepted
time: 71ms
memory: 7652kb

input:

198 199
bbboboooobooooobbobobbbbbbboobbboooboooooboboooobbboooobobbbboooobbbobboobobobbobobobbobbobooobobbobooobobobbobbbbbbbobobbbbobbbbbbbobbbboooboobbbbobbbbbbboobboooobboboobbobbooobbbobbboooboobobooobb
160 85
179 137
121 64
16 175
81 140
77 134
133 28
174 56
170 16
40 139
149 117
21 173
32 196
...

output:

49
273
377
462
387
79
1894
68
472
1523
0
357
514
1201
1172
562
747
451
498
2124
1835
190
194
120
148
2483
1970
64
1198
117
120
213
1688
123
2731
129
165
222
68
2367
150
178
597
269
156
301
109
119
122
577
1946
184
84
309
130
292
1333
1451
313
87
664
207
724
1172
706
252
752
239
162
125
252
256
245
1...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 96ms
memory: 7808kb

input:

1386 1998
obobobobbooboooooooobboooobbbboboobbbbobooboboooobobboobboooobbbobboboobooboobbobbbbbbboboooooooooooobobboobobbboobbbbobobobobbbbboobooobbobbooooboobooobbobooooobobobbbbbobbbbbobbobbbbbobbbobooooobooobobbobooobooooobobboobbobbobbbboobbobboobbbbbboobobobobobbobbbboooooobooooboobbbooobbboooo...

output:

1948
8498
2119
1572
29074
47195
10751
15880
4222
1221
1057
2356
3106
10786
1420
1245
3597
20548
1230
13220
1446
1328
1950
3498
14322
3165
23590
71510
3352
2100
189658
2339
3907
3284
121120
25167
1106
1957
19478
7489
273052
3782
16665
2543
840
1833
12910
3447
12976
2243
11051
2416
32494
1074
1470
143...

result:

ok 100 lines

Test #6:

score: 0
Accepted
time: 97ms
memory: 7972kb

input:

20000 19998
oooobboobboobooobbbbboobbboooboobbbbboobbbbbboobooboobbbbboooobbbooobobbobbobbobbboboobbobbbbbboobbobboobbbobbooobobbboboboooobooobboobboboobbobobbboobbbobbooooboobboboooobobbbobobbbboooobboboobbbobbobbbobboooobbboboobooboobbbobbobobbooobboooobooobbboboboobbbbbooboooobbbbooobooobbbboooob...

output:

9618
9527
9799
10267
10250
9970
9942
9749
9484
10163

result:

ok 10 lines

Test #7:

score: 0
Accepted
time: 110ms
memory: 12124kb

input:

200000 199999
ooooobbbooboooboooobbobbobbbobbbobbooboobbbobbobboooobbbboobobbboobbbbbbbobobbbbbbbooobobbbbobooooooobooobooboobbbobboobbooobobboobbobbbobbbboooobbooobobooobbbobbboobbbbbboboobbbobobbbbobbbbbbooobbbobbboobooboooobooobobbbobobboobobboboobboboooobooboobboobbooobobbobbboobboobobbbbobooooo...

output:

100506

result:

ok single line: '100506'

Test #8:

score: -100
Time Limit Exceeded

input:

2000 119368
oooobooobboboobbbbbbboobboboooboobbooobboobbbbbbobboooobooobooobooobbooboobobobbbooboobooooooobbboobobboobbobboboobobbobbbobbboobboobooobbbobbooobbobbbbobobbobbobbobbboobboobobobbbooboobobobobbobobobobbobbooobbooobobboooobbbobooooboooooobbobbboboboobboobooboboobooooobboobobbbbbbbooobobbb...

output:


result: