QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403990#8213. Graffitii_am_noob#WA 3ms10820kbC++142.3kb2024-05-03 01:58:512024-05-03 01:58:51

Judging History

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

  • [2024-05-03 01:58:51]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：10820kb
查看
  • [2024-05-03 01:58:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int N=300005,mod=1000000007;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return 1ll*x*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}

int n;
ll dp[N][2][2],res=-4e18;
vector<int> adj[N],vec;

void dfs(int u, int fa){
    for(auto v: adj[u]) if(v!=fa) dfs(v,u);
    for(int x: {0,1}) for(int y: {0,1}) dp[u][x][y]=-4e18;
    for(int x: {0,1}){
        ll base=0;
        for(auto v: adj[u]) if(v!=fa) base+=dp[v][0][x];
        vector<ll> vec2;
        for(auto v: adj[u]) if(v!=fa) vec2.pb(dp[v][1][x]-dp[v][0][x]);
        sort(all(vec2)),reverse(all(vec2));
        for(int i=0; i<=sz(vec2); ++i){
            for(int y: {0,1}){
                int cnt0=sz(vec2)-i,cnt1=i;
                if(y) cnt1++;
                else if(fa>=0) cnt0++;
                ll de=base;
                if(vec[1]==x){
                    if(vec[2]==2) de+=1ll*(cnt0/2)*((cnt0+1)/2);
                    else if(vec[0]!=vec[2]) de+=1ll*cnt0*cnt1;
                    else de+=1ll*cnt0*(cnt0-1);
                }
                if(fa>=0) dp[u][x][y]=max(dp[u][x][y],de);
                else res=max(res,de);
            }
            if(i==sz(vec2)) break;
            base+=vec2[i];
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    {
        string s; cin >> s;
        int cur=0;
        for(int i=0; i<sz(s); ++i){
            bool flag=0;
            for(int j=0; j<i; ++j) if(s[i]==s[j]){
                vec.pb(vec[j]);
                flag=1;
                break;
            }
            if(!flag) vec.pb(cur++);
        }
    }
    for(int i=0; i<n-1; ++i){
        int u,v; cin >> u >> v; u--,v--;
        adj[u].pb(v),adj[v].pb(u);
    }
    if(sz(vec)==1){
        cout << n << "\n";
        return 0;
    }
    if(sz(vec)==2){
        cout << (n-1)*(vec[0]==vec[1]?2:1) << "\n";
        return 0;
    }
    dfs(0,-1);
    cout << res << "\n";
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10596kb

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10800kb

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 10608kb

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 10524kb

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: 3ms
memory: 10760kb

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: 10820kb

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: 10588kb

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: 10616kb

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: 10584kb

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: 10508kb

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: 3ms
memory: 10788kb

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: 10788kb

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: 10788kb

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: 3ms
memory: 10592kb

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'
English 繁體中文 简体中文

Server Time: 2024-12-12 05:56:00 | OpenSource Project