QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#578362#8213. Graffitiucup-team3519#WA 0ms3824kbC++202.3kb2024-09-20 18:38:452024-09-20 18:38:45

Judging History

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

  • [2024-09-20 18:38:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3824kb
  • [2024-09-20 18:38:45]
  • 提交

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'