QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #340214 | #8213. Graffiti | ucup-team191# | WA | 4ms | 19548kb | C++23 | 3.0kb | 2024-02-28 19:17:09 | 2024-02-28 19:17:09 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 3e5 + 500;
string s;
int n;
vector < int > v[N];
ll dp[N][2][3];
ll f010(int x, int ja, int par, int lst) {
if(dp[x][ja][par] != -1) return dp[x][ja][par];
ll ret = 0;
if(ja == 0) {
for(int y : v[x]) {
if(y == lst) continue;
ret += max(f010(y, 0, 0, x), f010(y, 1, 0, x));
}
} else {
vector < ll > vv;
ll bs = 0;
for(int y : v[x]) {
if(y == lst) continue;
ll dp0 = f010(y, 0, 1, x) + (par == 0);
ll dp1 = f010(y, 1, 1, x);
vv.PB(dp0 - dp1);
bs += dp1;
}
sort(vv.rbegin(), vv.rend());
ret = bs;
for(int k = 0;k < (int)vv.size();k++) {
bs += vv[k];
ret = max(ret, bs + (ll)k * (k + 1) / 2);
}
}
return dp[x][ja][par] = ret;
}
ll f011(int x, int ja, int par, int lst) {
if(dp[x][ja][par] != -1) return dp[x][ja][par];
ll ret = 0;
if(ja == 0) {
for(int y : v[x]) {
if(y == lst) continue;
ret += max(f011(y, 0, 0, x), f011(y, 1, 0, x));
}
} else {
vector < ll > vv;
ll bs = 0;
for(int y : v[x]) {
if(y == lst) continue;
ll dp0 = f011(y, 0, 1, x) + (par == 1);
ll dp1 = f011(y, 1, 1, x) + (par == 0);
vv.PB(dp0 - dp1);
bs += dp1;
}
sort(vv.rbegin(), vv.rend());
ret = bs;
for(int k = 0;k < (int)vv.size();k++) {
bs += vv[k];
ret = max(ret, bs + (ll)k * ((int)vv.size() - k));
}
}
return dp[x][ja][par] = ret;
}
ll pos(ll k) {
return (ll)((k + 1) / 2) * ((k + 2) / 2);
}
ll f012(int x, int ja, int par, int lst) {
if(dp[x][ja][par] != -1) return dp[x][ja][par];
ll ret = 0;
if(ja == 0) {
for(int y : v[x]) {
if(y == lst) continue;
ret += max(f012(y, 0, 0, x), f012(y, 1, 0, x));
}
} else {
vector < ll > vv;
ll bs = 0;
for(int y : v[x]) {
if(y == lst) continue;
ll dp0 = f012(y, 0, 1, x);
ll dp1 = f012(y, 1, 1, x);
vv.PB(dp0 - dp1);
bs += dp1;
}
sort(vv.rbegin(), vv.rend());
ret = bs;
for(int k = 0;k < (int)vv.size();k++) {
bs += vv[k];
ret = max(ret, bs + (par == 0 ? pos(k + 1) : pos(k)));
}
}
return dp[x][ja][par] = ret;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> s;
for(int i = 1;i < n;i++) {
int x, y; cin >> x >> y;
v[x].PB(y), v[y].PB(x);
}
if((int)s.size() <= 2) {
cout << (n - ((int)s.size() == 2)) * (1 + ((int)s.size() == 2 && s[0] == s[1])) << endl;
return 0;
}
if(s[0] == s[1] && s[1] == s[2]) {
ll ans = 0;
for(int i = 1;i <= n;i++)
ans += (ll)v[i].size() * (v[i].size() - 1);
cout << ans << endl;
return 0;
}
if(s[0] == s[2]) {
cout << 2LL * max(f010(1, 0, 2, 1), f010(1, 1, 2, 1)) << endl;
} else if(s[0] == s[1] || s[1] == s[2]) {
cout << max(f011(1, 0, 2, 1), f011(1, 1, 2, 1)) << endl;
} else {
cout << max(f012(1, 0, 2, 1), f012(1, 1, 2, 1)) << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18036kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 18992kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 4ms
memory: 18888kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 3ms
memory: 19236kb
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: 0ms
memory: 18336kb
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: 2ms
memory: 17928kb
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: 3ms
memory: 19120kb
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: 3ms
memory: 19548kb
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: 0ms
memory: 18456kb
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: 3ms
memory: 18012kb
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: -100
Wrong Answer
time: 0ms
memory: 17904kb
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:
53
result:
wrong answer 1st numbers differ - expected: '54', found: '53'