QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360345#8213. GraffitiinstallbWA 1ms6064kbC++234.8kb2024-03-21 17:40:512024-03-21 17:40:52

Judging History

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

  • [2024-03-21 17:40:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6064kb
  • [2024-03-21 17:40:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define M 300005
int n,m,ty;
char S[5];
vector<int>edge[M];
using ll = long long;
ll f[M][3][3];
using pll = pair<ll,ll>;
vector<pll>A;
ll solve1(){//C(#a,2) + sum
    vector<ll>p;
    ll ret = 0, s = 0;
    for(auto [x,y]: A) 
        s += y, p.push_back(x-y);
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    ret = s;
    for(int i=0;i<p.size();i++){
        s += p[i];
        ret = max(ret,(1ll*(i+1)*((int)p.size()-i-1))+s);
    }
    return ret;
}
ll solve3(){//C(#a,2) + sum
    vector<ll>p;
    ll ret = 0, s = 0;
    for(auto [x,y]: A) 
        s += y, p.push_back(x-y);
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    ret = s;
    for(int i=0;i<p.size();i++){
        s += p[i];
        ret = max(ret,(1ll*(i+1)*i>>1)+s);
    }
    return ret;
}
using tll = tuple<ll,ll,ll>;
vector<tll>B;
const ll inf = 1e16;
ll solve2(){
    if(B.empty()) return 0ll;
    vector<ll>p;
    ll ret = 0, sumz = 0,v = -inf;
    for(auto [x,y,z]: B){
        sumz += y;
        if(v == -inf) v = x - z;
        else assert(v == x-z);
        p.push_back(z - y);
    }
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    static ll pre[M];
    pre[0]=0;
    for(int i=0;i<p.size();i++)pre[i+1] = pre[i] + p[i];
    ret = sumz;
    // cout<<pre[n]<<' '<<v<<endl;
    for(int i=0;i<p.size();i++){
        int n = (int)p.size() - i; 
        int p = max(0,(n-1)>>1);
        ret = max(ret,1ll*p*(n-p) + sumz + max(pre[n] + v*(n-p),pre[n] + v*p));
        // cout<<p<<endl;
        p++;
        if(p<=n)ret = max(ret,1ll*p*(n-p) + sumz + max(pre[n] + v*(n-p),pre[n] + v*p));
    }
    // for(auto [x,y,z]: B)cout<<x<<','<<y<<','<<z<<endl;
    // cout<<ret<<endl;
    return ret;
}
void dfs(int F,int now){
    for(int &to:edge[now])if(to!=F)dfs(now,to);
    if(ty == 3){
        for(int a=0;a<2;a++)
            for(int b=0;b<2;b++){
                if(a == 1){
                    A.clear();
                    for(int &to:edge[now])if(to!=F)
                        A.push_back(pll(f[to][0][a]+(b==0),f[to][1][a]));
                    f[now][a][b] = solve3();
                }else {
                    for(int &to:edge[now])if(to!=F)
                        f[now][a][b] += max(f[to][0][a],f[to][1][a]);
                }
            }
    }else if(ty == 2){
        for(int a=0;a<2;a++)
            for(int b=0;b<2;b++){
                if(a == 0){
                    A.clear();
                    for(int &to:edge[now])if(to!=F)
                        A.push_back(pll(f[to][0][a]+(b==1),f[to][1][a]+(b==0)));
                    f[now][a][b] = solve1();
                }else {
                    for(int &to:edge[now])if(to!=F)
                        f[now][a][b] += max(f[to][0][a],f[to][1][a]);
                }
            }
    }else{
        for(int a=0;a<3;a++)
            for(int b=0;b<3;b++){
                if(a == 1){
                    B.clear();
                    for(int &to:edge[now])if(to!=F)
                        B.push_back(tll(f[to][0][a]+(b==2),f[to][1][a],f[to][2][a]+(b==0)));
                    f[now][a][b] = solve2();
                }else {
                    for(int &to:edge[now])if(to!=F)
                        f[now][a][b] += max(f[to][2][a],max(f[to][0][a],f[to][1][a]));
                }
            }
    }
}
ll redfs(int F,int now,int flg){
    ll ret = 0,sz=edge[now].size();
    // if(flg)cout<<now<<' '<<sz<<endl;
    if(flg) ret += sz*(sz-1);
    for(int &to:edge[now])if(to!=F)
        ret += redfs(now,to,!flg);
    return ret;
}
int main(){
    cin>>n;
    scanf("%s",S+1);
    m=strlen(S+1);
    if(m==1)cout<<n<<endl;
    else if(m==2)cout<<n-1<<endl;
    if(m<=2)return 0;
    for(int a,b,i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    if(S[1] == S[2] && S[1] == S[3]){
        ll ans = 0;
        for(int i=1;i<=n;i++)
            ans += 1ll*edge[i].size()*((int)edge[i].size()-1)>>1;
        return cout<<ans*2<<endl,0;
    }else if(S[1] == S[3] && S[1] != S[2]) S[1]='a',S[2]='b',S[3]='a',ty=3;
    else if(S[1]!=S[2] && S[2]!=S[3] && S[1]!=S[3])S[1]='a',S[2]='b',S[3]='c',ty=1;
    else S[1]='a',S[2]='a',S[3]='b',ty=2;
    dfs(0,1);
    if(ty == 1){
        cout<<max(f[1][0][1],max(f[1][1][1],f[1][2][1]))<<endl;
    }else if(ty == 2){
        ll ans = 0;
        A.clear();
        for(int &to:edge[1])
            A.push_back(pll(f[to][0][0],f[to][1][0]));
        ans = solve1();
        
        ll s = 0;
        for(int &to:edge[1])
            s += max(f[to][0][1],f[to][1][1]);
        ans = max(ans,s);
        cout<<ans<<endl;
    }else{
        cout<<max(f[1][0][1],f[1][1][1])*2<<endl;
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 6060kb

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5760kb

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5664kb

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5820kb

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: 1ms
memory: 5836kb

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: 1ms
memory: 5764kb

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: 1ms
memory: 6064kb

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: 1ms
memory: 5844kb

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: 1ms
memory: 5768kb

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: 1ms
memory: 5784kb

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: 1ms
memory: 6064kb

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: 1ms
memory: 5844kb

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: 1ms
memory: 5840kb

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: 1ms
memory: 5772kb

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: 1ms
memory: 5772kb

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

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: 1ms
memory: 5744kb

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: 1ms
memory: 6028kb

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: 1ms
memory: 6060kb

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: 1ms
memory: 5760kb

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: 1ms
memory: 5828kb

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: 1ms
memory: 5752kb

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'