QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321024 | #8213. Graffiti | ucup-team087# | WA | 84ms | 22340kb | C++14 | 4.0kb | 2024-02-04 02:19:02 | 2024-02-04 02:19:02 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
constexpr Int INF = 1001001001001001001LL;
int N;
int WLen;
char W[10];
vector<int> A, B;
string S;
vector<vector<int>> graph;
Int dp[300'010][2][2];
void dfs(int u, int p) {
for (const int v : graph[u]) if (p != v) {
dfs(v, u);
}
for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) {
dp[u][x][y] = -INF;
if (y == 0) {
Int sum = 0;
for (const int v : graph[u]) if (p != v) {
sum += max(dp[v][y][0], dp[v][y][1]);
}
dp[u][x][y] = sum;
} else {
Int base = 0;
vector<Int> diffs;
for (const int v : graph[u]) if (p != v) {
base += dp[v][y][0];
diffs.push_back(dp[v][y][1] - dp[v][y][0]);
}
sort(diffs.begin(), diffs.end(), greater<Int>{});
const Int len = diffs.size();
Int score = base;
for (Int k = 0; ; ++k) {
Int cnt[2] = {len - k, k};
++cnt[x];
Int gain = 0;
if (false) {
} else if (S == "BBB") {
gain = cnt[1] * (cnt[1] - 1);
} else if (S == "ABB") {
gain = cnt[0] * cnt[1];
} else if (S == "ABA") {
gain = cnt[0] * (cnt[0] - 1);
} else if (S == "ABC") {
gain = (cnt[0] / 2) * ((cnt[0] + 1) / 2);
} else {
assert(false);
}
chmax(dp[u][x][y], score + gain);
if (k == len) break;
score += diffs[k];
}
}
assert(dp[u][x][y] >= 0);
}
// cerr<<u<<": ";for(int x=0;x<2;++x)for(int y=0;y<2;++y)cerr<<dp[u][x][y]<<" ";cerr<<endl;
}
int main() {
for (; ~scanf("%d", &N); ) {
scanf("%s", W);
WLen = strlen(W);
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
Int ans = -INF;
if (WLen == 1) {
ans = N;
} else if (WLen == 2) {
ans = N - 1;
} else if (WLen == 3) {
if (N < 3) {
ans = 0;
} else {
if (W[0] == W[1] && W[1] == W[2]) {
S = "BBB";
} else if (W[0] == W[1] || W[1] == W[2]) {
S = "ABB";
} else if (W[0] == W[2]) {
S = "ABA";
} else {
S = "ABC";
}
cerr<<"S = "<<S<<endl;
int r = -1;
for (int u = 0; u < N; ++u) if (graph[u].size() == 1) {
r = u;
break;
}
assert(~r);
dfs(r, -1);
for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) {
chmax(ans, dp[graph[r][0]][x][y]);
}
}
} else {
assert(false);
}
printf("%lld\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
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: 3836kb
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: 3896kb
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: 3832kb
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: 3824kb
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: 3828kb
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: 3840kb
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: 3840kb
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: 3836kb
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: 3800kb
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: 0ms
memory: 3824kb
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: 0ms
memory: 3828kb
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: 3832kb
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: 0ms
memory: 3812kb
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: 0ms
memory: 4116kb
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: 0ms
memory: 4092kb
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: 0ms
memory: 3836kb
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: 84ms
memory: 22312kb
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: -100
Wrong Answer
time: 82ms
memory: 22340kb
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:
299999
result:
wrong answer 1st numbers differ - expected: '599998', found: '299999'