QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62134 | #2827. Autobiography | xuancx# | TL | 171ms | 19012kb | C++20 | 1.5kb | 2022-11-17 15:09:15 | 2022-11-17 15:09:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
char c[N];
vector<int> vt[N];
vector<int> b[N];
ll dfs(int u, int fa, int ffa, char now, int height)
{
if (height == 3)
{
// cout << u << " " << b[u].size() << endl;
return b[u].size() - 1;
}
ll ans = 0;
for (auto v : vt[u])
{
if (v == fa || v == ffa)
continue;
if (c[v] == now)
continue;
ans += dfs(v, u, fa, c[v], height + 1);
}
return ans;
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
vector<int> bb;
for (int i = 1; i <= n; i++)
{
b[i].clear();
vt[i].clear();
cin >> c[i];
if (c[i] == 'b')
bb.push_back(i);
}
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (c[u] == 'b' && c[v] == 'o')
{
b[u].push_back(v);
vt[u].push_back(v);
vt[v].push_back(u);
}
else if (c[u] == 'o' && c[v] == 'b')
{
b[v].push_back(u);
vt[u].push_back(v);
vt[v].push_back(u);
}
}
ll ans = 0;
for (int i = 0; i < bb.size(); i++)
{
ans += dfs(bb[i], -1, -1, 'b', 1);
}
printf("%lld\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13088kb
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: 104ms
memory: 12896kb
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: 61ms
memory: 12924kb
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: 45ms
memory: 13048kb
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: 37ms
memory: 13112kb
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: 49ms
memory: 14456kb
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: 78ms
memory: 19012kb
input:
200000 199999 ooooobbbooboooboooobbobbobbbobbbobbooboobbbobbobboooobbbboobobbboobbbbbbbobobbbbbbbooobobbbbobooooooobooobooboobbbobboobbooobobboobbobbbobbbboooobbooobobooobbbobbboobbbbbboboobbbobobbbbobbbbbbooobbbobbboobooboooobooobobbbobobboobobboboobboboooobooboobboobbooobobbobbboobboobobbbbobooooo...
output:
100506
result:
ok single line: '100506'
Test #8:
score: 0
Accepted
time: 112ms
memory: 14012kb
input:
2000 119368 oooobooobboboobbbbbbboobboboooboobbooobboobbbbbbobboooobooobooobooobbooboobobobbbooboobooooooobbboobobboobbobboboobobbobbbobbboobboobooobbbobbooobbobbbbobobbobbobbobbboobboobobobbbooboobobobobbobobobobbobbooobbooobobboooobbbobooooboooooobbobbboboboobboobooboboobooooobboobobbbbbbbooobobbb...
output:
1677952657
result:
ok single line: '1677952657'
Test #9:
score: 0
Accepted
time: 171ms
memory: 14052kb
input:
5000 98161 oooobobobooobbbbbooooobbboobbobbbboobboobobbobooboobboobbbbooobbobobobbobbobooboobbobobbbbobbooobbboooobobooobbbooboobobbbboboobbbboooobbooboobobooobobooboboobboobbbboobbobobooobbbbbobbbbbobobbobbobbboobobbbbbobooobboobbbboobbobbobooobbbbobbooooobooobbboooobbboboobboooobboobbobbobbobooobo...
output:
1234650182
result:
ok single line: '1234650182'
Test #10:
score: -100
Time Limit Exceeded
input:
40005 200000 ooooobbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...