QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21691 | #2827. Autobiography | s8194272# | AC ✓ | 52ms | 13276kb | C++14 | 1.8kb | 2022-03-08 14:09:39 | 2022-05-08 03:57:04 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define int long long
#define fi first
#define se second
#define max Max
#define min Min
#define abs Abs
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define fan(x) (((x-1)^1)+1)
#define mp(x,y) make_pair(x,y)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
return ans*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x/10) write(x/10);
putchar((char)(x%10)+'0');
}
template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a<b?a:b;}
template<typename T,typename TT> inline T Max(T a,TT b){return a<b?b:a;}
const int N=2e5+5;
int n,m,nm[N],ans;
char s[N];
struct Edge
{
int v,ne;
}e[N*2];
int head[N],tot;
inline void add(int u,int v)
{
e[++tot]=(Edge){v,head[u]};
head[u]=tot;
}
signed main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
scanf("%s",s+1);ans=0;
for(int i=1;i<=m;++i)
{
int u=read(),v=read();
add(u,v);add(v,u);
}
for(int i=1;i<=n;++i)
if(s[i]=='b')
for(int j=head[i];j;j=e[j].ne)
if(s[e[j].v]=='o')
nm[i]++,nm[e[j].v]++;
for(int i=1;i<=n;++i)
if(s[i]=='o')
for(int j=head[i];j;j=e[j].ne)
if(s[e[j].v]=='b')
ans+=(nm[i]-1)*(nm[e[j].v]-1);
write(ans);puts("");
for(int i=1;i<=n;++i)
nm[i]=0,head[i]=0;
tot=0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7616kb
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: 17ms
memory: 5764kb
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: 10ms
memory: 7808kb
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: 15ms
memory: 7840kb
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: 11ms
memory: 5836kb
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: 29ms
memory: 8340kb
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: 52ms
memory: 13276kb
input:
200000 199999 ooooobbbooboooboooobbobbobbbobbbobbooboobbbobbobboooobbbboobobbboobbbbbbbobobbbbbbbooobobbbbobooooooobooobooboobbbobboobbooobobboobbobbbobbbboooobbooobobooobbbobbboobbbbbboboobbbobobbbbobbbbbbooobbbobbboobooboooobooobobbbobobboobobboboobboboooobooboobboobbooobobbobbboobboobobbbbobooooo...
output:
100506
result:
ok single line: '100506'
Test #8:
score: 0
Accepted
time: 15ms
memory: 11920kb
input:
2000 119368 oooobooobboboobbbbbbboobboboooboobbooobboobbbbbbobboooobooobooobooobbooboobobobbbooboobooooooobbboobobboobbobboboobobbobbbobbboobboobooobbbobbooobbobbbbobobbobbobbobbboobboobobobbbooboobobobobbobobobobbobbooobbooobobboooobbbobooooboooooobbobbboboboobboobooboboobooooobboobobbbbbbbooobobbb...
output:
1677952657
result:
ok single line: '1677952657'
Test #9:
score: 0
Accepted
time: 12ms
memory: 11860kb
input:
5000 98161 oooobobobooobbbbbooooobbboobbobbbboobboobobbobooboobboobbbbooobbobobobbobbobooboobbobobbbbobbooobbboooobobooobbbooboobobbbboboobbbboooobbooboobobooobobooboboobboobbbboobbobobooobbbbbobbbbbobobbobbobbboobobbbbbobooobboobbbboobbobbobooobbbbobbooooobooobbboooobbboboobboooobboobbobbobbobooobo...
output:
1234650182
result:
ok single line: '1234650182'
Test #10:
score: 0
Accepted
time: 14ms
memory: 10656kb
input:
40005 200000 ooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
31999200000
result:
ok single line: '31999200000'
Test #11:
score: 0
Accepted
time: 16ms
memory: 11864kb
input:
20010 200000 oooooooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
35998200000
result:
ok single line: '35998200000'
Test #12:
score: 0
Accepted
time: 32ms
memory: 10212kb
input:
10020 200000 oooooooooooooooooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
37996200000
result:
ok single line: '37996200000'
Test #13:
score: 0
Accepted
time: 18ms
memory: 11892kb
input:
4050 200000 oooooooooooooooooooooooooooooooooooooooooooooooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39190200000
result:
ok single line: '39190200000'
Test #14:
score: 0
Accepted
time: 26ms
memory: 11960kb
input:
2100 200000 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39580200000
result:
ok single line: '39580200000'
Test #15:
score: 0
Accepted
time: 26ms
memory: 11932kb
input:
1000 200000 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
31873020142
result:
ok single line: '31873020142'