QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #323227 | #8213. Graffiti | karuna | WA | 86ms | 20556kb | C++20 | 2.0kb | 2024-02-08 23:11:38 | 2024-02-08 23:11:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 303030;
int n, q;
vector<int> g[MAXN];
ll dp[2][2][MAXN];
void dfs(int p, int v) {
for (int x : g[v]) if (p != x) {
dfs(v, x);
}
for (int s = 0; s < 2; s++) for (int t = 0; t < 2; t++) {
vector<ll> V;
ll tot = 0;
for (int x : g[v]) if (p != x) {
tot += dp[t][1][x];
V.push_back(dp[t][0][x] - dp[t][1][x]);
}
sort(V.rbegin(), V.rend());
for (int a = 0; a <= V.size(); a++) {
int b = V.size() - a;
ll val = tot;
if (q == 1) {
if (s == 0 && t == 1) val += 2 * a;
if (t == 1) val += (ll)a * (a - 1);
}
if (q == 2) {
if (s == 0 && t == 0) val += b;
if (s == 1 && t == 0) val += a;
if (t == 0) val += (ll)a * b;
}
if (q == 3) {
if (s == 0 && t == 1) val += (ll)((a + 1) / 2) * ((a + 2) / 2);
else if (t == 1) val += (ll)(a / 2) * ((a + 1) / 2);
}
dp[s][t][v] = max(dp[s][t][v], val);
if (a != V.size()) {
tot += V[a];
}
}
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
string S; cin >> S;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
if (S.size() == 1) return !(cout << n << '\n');
if (S.size() == 2) {
if (S[0] == S[1])
return !(cout << 2 * (n - 1) << '\n');
else
return !(cout << n - 1 << '\n');
}
if (S[0] == S[2]) {
if (S[0] == S[1]) {
ll ans = 0;
for (int v = 1; v <= n; v++) {
ans += (ll)g[v].size() * (g[v].size() - 1) / 2;
}
return !(cout << ans << '\n');
}
else q = 1;
}
else {
if (S[0] == S[1] || S[1] == S[2])
q = 2;
else
q = 3;
}
int p, v;
for (int i = 1; i <= n; i++) {
if (g[i].size() == 1) {
p = i;
v = g[p][0];
break;
}
}
dfs(p, v);
ll ans = 0;
for (int s = 0; s < 2; s++) for (int t = 0; t < 2; t++) {
ans = max(ans, dp[s][t][v]);
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3808kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
5 bob 3 2 5 1 1 4 2 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
50 abc 23 14 24 25 1 3 47 46 2 26 22 41 34 19 7 14 50 24 29 38 17 25 4 26 35 37 21 14 11 4 13 27 8 25 5 10 20 27 44 27 15 39 19 9 30 12 38 27 39 27 41 40 14 48 32 7 16 37 3 13 42 5 48 27 49 25 6 5 26 9 31 17 36 7 43 29 9 5 45 9 18 9 40 42 27 5 25 42 46 10 37 42 12 48 28 26 33 5
output:
37
result:
ok 1 number(s): "37"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
50 abc 14 26 46 47 10 13 30 19 33 46 32 50 39 6 35 13 8 5 28 3 2 21 17 22 22 6 5 20 19 3 38 3 16 2 18 34 13 6 47 6 9 28 1 2 37 47 50 10 12 34 40 19 42 19 26 46 43 3 44 47 31 47 49 18 45 34 27 13 7 34 6 34 3 45 11 44 21 13 29 24 15 40 48 39 24 6 41 47 23 27 36 21 25 21 4 20 20 44
output:
37
result:
ok 1 number(s): "37"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
50 abc 11 3 14 46 37 47 18 33 12 46 40 41 23 17 49 48 27 26 13 5 26 41 43 16 25 47 46 9 39 13 38 4 36 18 28 40 50 26 10 38 9 50 15 6 24 16 19 16 48 26 6 50 31 16 29 16 7 26 35 14 17 46 21 5 22 38 2 15 4 17 30 34 16 41 45 17 47 50 44 16 33 26 32 34 1 25 3 46 20 16 5 32 42 14 8 48 41 34
output:
44
result:
ok 1 number(s): "44"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
50 abc 9 7 43 49 26 3 14 11 17 43 23 35 19 25 44 25 2 1 10 28 4 46 21 22 15 43 39 25 16 38 38 23 34 29 47 49 46 35 5 39 25 35 32 23 27 37 3 32 37 24 20 13 33 25 1 29 30 11 31 34 18 31 50 37 13 48 22 23 8 10 41 24 42 46 36 37 48 43 49 31 40 41 12 35 24 34 45 7 35 31 7 31 11 44 28 1 6 19
output:
34
result:
ok 1 number(s): "34"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
50 abc 31 6 36 20 32 42 47 14 24 21 27 39 14 22 26 47 44 45 30 28 15 18 1 14 42 38 20 35 17 25 4 18 25 47 40 3 28 7 48 33 2 41 10 33 22 38 41 38 9 40 35 41 16 45 49 32 19 28 21 32 34 29 46 25 13 14 23 15 3 38 18 12 45 35 29 20 43 18 6 3 8 12 12 41 50 12 7 42 5 36 33 36 39 16 11 16 37 41
output:
30
result:
ok 1 number(s): "30"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
50 abc 50 18 10 32 38 18 47 13 31 6 49 18 45 47 42 4 7 18 18 27 36 13 12 13 41 12 35 8 6 40 16 8 4 22 14 44 25 2 28 18 3 27 34 32 5 27 43 5 33 11 23 24 2 18 21 39 46 5 8 49 32 19 20 28 22 12 11 5 15 38 44 7 9 5 19 49 1 16 30 50 48 25 40 11 24 27 26 5 37 50 17 24 13 5 39 26 29 27
output:
38
result:
ok 1 number(s): "38"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
51 abb 7 35 1 48 32 42 45 15 13 39 14 43 9 2 34 37 23 24 47 36 36 35 41 22 50 49 49 44 28 42 48 43 20 37 22 21 10 38 6 35 29 17 35 24 19 51 21 44 38 4 11 17 33 42 37 50 44 38 12 17 43 38 3 49 8 12 16 49 5 15 40 31 24 4 15 50 39 44 42 35 27 21 51 50 18 13 30 4 26 29 31 22 46 49 17 38 25 49 2 26
output:
54
result:
ok 1 number(s): "54"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
51 abb 4 33 29 28 44 34 31 46 46 17 27 48 25 35 45 19 36 40 35 51 22 36 43 9 26 47 21 36 12 17 51 50 13 44 3 34 19 36 15 32 47 28 1 3 2 40 33 46 5 30 48 39 41 15 8 20 14 46 34 27 40 17 24 2 38 10 9 17 30 19 32 17 16 21 23 9 42 34 6 15 10 31 11 28 18 34 49 40 37 34 50 19 28 17 39 40 20 19 7 24
output:
57
result:
ok 1 number(s): "57"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
51 abb 27 37 40 37 33 22 3 29 9 28 14 28 38 17 49 47 36 29 46 10 6 11 11 47 37 18 20 22 39 28 29 28 1 7 32 42 24 30 2 45 16 7 45 29 42 39 43 42 5 37 22 49 34 31 4 29 30 22 41 29 18 22 50 22 25 28 7 42 26 30 51 14 19 13 8 49 35 22 48 14 12 42 21 35 23 50 44 42 31 22 13 39 17 37 10 31 15 37 28 49
output:
70
result:
ok 1 number(s): "70"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
51 abb 7 43 11 39 8 5 47 44 25 49 9 30 40 3 36 17 13 41 16 50 44 10 12 7 33 44 5 2 35 7 22 45 19 43 18 32 42 19 31 10 45 29 3 19 46 48 39 2 34 25 14 43 2 19 21 7 32 16 51 27 6 24 43 41 27 32 48 15 23 43 17 16 50 43 24 28 1 13 38 19 37 19 49 2 26 10 28 43 30 19 4 22 20 42 15 19 29 44 10 19
output:
63
result:
ok 1 number(s): "63"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
51 aba 44 6 9 7 1 50 24 38 26 11 30 2 6 21 34 43 49 11 13 4 42 21 5 38 22 3 18 3 45 34 28 26 38 43 27 21 37 27 16 42 2 23 43 21 32 21 29 28 19 13 51 13 15 40 20 1 36 46 10 3 12 11 25 21 47 6 33 7 39 22 4 38 8 27 35 38 48 50 41 31 50 21 31 26 23 26 17 24 40 21 46 44 7 32 3 8 11 43 14 11
output:
132
result:
ok 1 number(s): "132"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
52 aba 19 7 11 48 4 6 5 27 46 50 6 37 50 23 12 40 37 23 13 23 32 38 22 44 52 5 34 50 26 38 35 10 51 20 7 26 41 6 15 26 39 10 10 40 3 50 33 29 30 14 45 50 14 27 21 27 42 29 49 44 31 27 18 5 36 42 16 11 29 28 24 12 8 50 38 5 43 10 48 52 1 52 47 26 40 32 2 3 44 27 28 38 20 26 23 5 17 27 9 43 25 46
output:
116
result:
ok 1 number(s): "116"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
52 aba 10 43 2 40 24 9 47 35 42 44 1 18 7 18 3 40 28 4 52 25 6 13 33 18 35 19 49 2 16 39 26 3 32 8 4 44 50 22 11 30 41 6 19 39 18 39 14 36 34 44 36 4 17 34 45 21 12 17 25 36 51 39 29 8 30 23 9 8 46 11 37 2 23 13 20 13 44 51 15 37 43 27 40 51 31 3 5 10 22 18 8 44 21 23 27 30 38 28 13 39 48 25
output:
88
result:
ok 1 number(s): "88"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
52 aba 48 38 40 22 49 23 37 3 6 12 43 42 26 22 30 39 8 7 25 7 47 41 44 11 52 1 13 1 41 14 19 41 23 39 35 13 32 19 38 13 39 41 2 27 51 21 31 19 21 9 29 36 9 39 16 27 15 22 24 42 18 30 42 9 36 30 4 7 27 9 17 5 22 9 50 30 20 16 46 52 28 21 5 16 3 1 33 22 7 28 10 21 12 34 34 39 11 39 1 11 45 11
output:
112
result:
ok 1 number(s): "112"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
52 aba 46 45 42 45 18 27 3 44 16 25 39 24 40 10 33 32 19 31 13 1 27 45 25 9 23 2 29 14 24 8 21 52 14 37 17 24 15 9 41 24 43 31 38 7 4 52 45 7 50 1 6 40 49 22 37 52 11 23 48 7 5 2 10 1 2 48 8 7 36 22 26 28 44 23 34 13 9 7 31 26 12 8 52 48 47 3 30 40 20 25 7 22 1 26 28 52 51 26 32 45 35 30
output:
106
result:
ok 1 number(s): "106"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
52 aba 36 34 23 29 28 11 2 47 33 26 16 37 27 46 52 3 8 14 44 15 51 47 37 7 34 29 50 27 12 47 6 18 20 21 17 14 18 13 10 3 49 17 13 3 42 22 30 13 46 43 5 19 9 18 11 14 38 51 21 46 40 50 39 19 48 22 43 19 24 19 19 14 22 41 45 37 15 41 26 11 31 46 4 43 35 15 3 19 41 43 32 11 29 47 1 7 47 43 7 14 25 28
output:
104
result:
ok 1 number(s): "104"
Test #21:
score: 0
Accepted
time: 85ms
memory: 20556kb
input:
300000 z 180011 260532 271217 191245 41791 255746 290587 278534 218547 277068 139010 241751 243632 263417 248223 222193 89717 215179 251082 231639 117314 8572 245286 297248 168750 266280 80957 255206 73540 12700 170796 282744 214088 139101 299056 232065 3541 39425 245901 203384 4354 21447 106700 295...
output:
300000
result:
ok 1 number(s): "300000"
Test #22:
score: 0
Accepted
time: 84ms
memory: 20392kb
input:
300000 aa 145612 276393 88541 108216 226040 100484 260244 139556 150893 213849 85295 33531 270499 248769 5250 51884 24539 76804 254304 165858 85779 118908 183955 155461 5230 80950 80213 95224 58182 122060 46066 288552 138127 46553 186220 182641 21451 14106 193341 35522 269820 212259 208311 40745 229...
output:
599998
result:
ok 1 number(s): "599998"
Test #23:
score: 0
Accepted
time: 24ms
memory: 10692kb
input:
123234 ab 5333 65911 93667 3824 117784 113995 122335 34180 100563 13017 2356 55265 68248 30680 67326 55966 55450 2923 86794 12061 49667 54440 46800 106814 4840 7419 53069 122499 34188 99215 18873 90062 115319 82268 1093 52619 108703 107429 40381 14308 91251 53870 7680 94995 90630 57256 78084 11866 3...
output:
123233
result:
ok 1 number(s): "123233"
Test #24:
score: -100
Wrong Answer
time: 86ms
memory: 20400kb
input:
300000 aaa 286864 6103 13963 130993 193857 266146 21588 192178 60950 206316 57174 172746 83177 159553 274512 266893 1479 82701 149984 220249 66444 38360 164961 269188 90561 160425 48372 223724 176008 89731 146829 119384 4625 131173 271552 74420 258647 63612 101816 202418 73996 284875 167169 62661 18...
output:
601347
result:
wrong answer 1st numbers differ - expected: '1202694', found: '601347'