QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578362 | #8213. Graffiti | ucup-team3519# | WA | 0ms | 3824kb | C++20 | 2.3kb | 2024-09-20 18:38:45 | 2024-09-20 18:38:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
typedef long long LL;
void solve() {
int n; cin >> n;
V<V<int>> e(n + 1);
string s; cin >> s;
for(int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
e[a].pb(b);
e[b].pb(a);
}
auto cal = [&](int x) -> LL {
if(s[0] == s[2]) return 1LL * x * (x - 1);
return 1LL * (x / 2) * (x - x / 2);
};
if(s.size() == 1) {
cout << n << endl;
return;
} else if(s.size() == 2) {
if(s[0] == s[1]) cout << 2 * (n - 1) << endl;
else cout << n - 1 << endl;
return;
} else if(s[0] == s[1] && s[1] == s[2]) {
LL ans = 0;
for(int i = 1; i <= n; i++) ans += cal(e[i].size());
cout << ans << endl;
return;
}
V<LL> dp_o_o(n + 1), dp_o_s(n + 1), dp_s(n + 1);
auto dfs = [&](int x, int p, auto dfs) -> void {
LL s_sum = 0;
LL base = 0;
V<LL> cost(1);
int cnt = 0;
for(auto y : e[x]) {
if(y == p) continue;
cnt++;
dfs(y, x, dfs);
s_sum += max(dp_o_s[y], dp_s[y]);
cost.pb(dp_o_o[y] - dp_s[y]);
base += dp_o_o[y];
}
sort(cost.begin() + 1, cost.end());
// for(auto x : cost) cout << x << " ";
// cout << endl;
dp_s[x] = s_sum;
if(s[0] == s[1] || s[1] == s[2]) {
for(int i = 0; i < cost.size(); i++) {
base -= cost[i];
// cout << base + cal(i) << endl;
dp_o_s[x] = max(dp_o_s[x], base + 1LL * (1 + i) * (cnt - i));
dp_o_o[x] = max(dp_o_o[x], base + 1LL * (i) * (cnt - i + 1));
}
} else {
for(int i = 0; i < cost.size(); i++) {
base -= cost[i];
// cout << base + cal(i) << endl;
dp_o_s[x] = max(dp_o_s[x], base + cal(i + 1));
dp_o_o[x] = max(dp_o_o[x], base + cal(i));
}
}
// cout << " x : " << x << " " << cost.size() << endl;
};
dfs(1, 0, dfs);
cout << max(dp_o_o[1], dp_s[1]) << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
// int t; cin >> t;
int t = 1;
while(t--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
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: 3528kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3512kb
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: 0ms
memory: 3536kb
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: 3620kb
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: 0ms
memory: 3616kb
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: 0ms
memory: 3548kb
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: 0ms
memory: 3600kb
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: 0ms
memory: 3588kb
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: -100
Wrong Answer
time: 0ms
memory: 3612kb
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:
64
result:
wrong answer 1st numbers differ - expected: '63', found: '64'