QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62119 | #2827. Autobiography | defathom# | TL | 188ms | 14292kb | C++14 | 1.1kb | 2022-11-17 14:43:01 | 2022-11-17 14:43:02 |
Judging History
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()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
while(scanf("%d%d",&n,&m)!=EOF)
{
cin>>s;
s=" "+s;
cnt=0;
for(int i=1;i<=n+5;++i)
head[i]=0;
ans=0;
while(m--)
{
int x,y;
scanf("%d%d",&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: 0ms
memory: 7700kb
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: 188ms
memory: 7556kb
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: 93ms
memory: 7648kb
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: 55ms
memory: 7612kb
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: 55ms
memory: 7628kb
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: 42ms
memory: 8028kb
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: 58ms
memory: 14292kb
input:
200000 199999 ooooobbbooboooboooobbobbobbbobbbobbooboobbbobbobboooobbbboobobbboobbbbbbbobobbbbbbbooobobbbbobooooooobooobooboobbbobboobbooobobboobbobbbobbbboooobbooobobooobbbobbboobbbbbboboobbbobobbbbobbbbbbooobbbobbboobooboooobooobobbbobobboobobboboobboboooobooboobboobbooobobbobbboobboobobbbbobooooo...
output:
100506
result:
ok single line: '100506'
Test #8:
score: -100
Time Limit Exceeded
input:
2000 119368 oooobooobboboobbbbbbboobboboooboobbooobboobbbbbbobboooobooobooobooobbooboobobobbbooboobooooooobbboobobboobbobboboobobbobbbobbboobboobooobbbobbooobbobbbbobobbobbobbobbboobboobobobbbooboobobobobbobobobobbobbooobbooobobboooobbbobooooboooooobbobbboboboobboobooboboobooooobboobobbbbbbbooobobbb...