QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#321024#8213. Graffitiucup-team087#WA 84ms22340kbC++144.0kb2024-02-04 02:19:022024-02-04 02:19:02

Judging History

你现在查看的是最新测评结果

  • [2024-02-04 02:19:02]
  • 评测
  • 测评结果:WA
  • 用时:84ms
  • 内存:22340kb
  • [2024-02-04 02:19:02]
  • 提交

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'