QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414483#8213. Graffitiucup-team1231#WA 1ms5660kbC++204.0kb2024-05-19 03:32:172024-05-19 03:32:17

Judging History

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

  • [2024-05-19 03:32:17]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：5660kb
查看
  • [2024-05-19 03:32:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long long int LLI;
#define SZ 300099
int n; string w;
vi adj[SZ];
ll ans;
namespace AB {
ll f[SZ][2];
void dfs(int x,int fa=0) {
    for(auto b:adj[x]) if(b!=fa) {
        dfs(b,x);
    }
    for(int o=0;o<2;++o) {
        ll&out=f[x][o];
        vector<ll> ee;
        ll F=0;
        for(auto b:adj[x]) if(b!=fa) {
            F+=f[b][0];
            ee.push_back(f[b][1]-f[b][0]);
        }
        sort(ee.begin(),ee.end());
        reverse(ee.begin(),ee.end());
        for(int i=0;i<=ee.size();++i) {
            if(i) F+=ee[i-1];
            int c[2]={ee.size()-i,i};
            out=max(out,F+c[!o]);
        }
    }
    if(!fa)
        ans=max(f[1][0],f[1][1]);
}
}
namespace ABA {
ll f[SZ][2][2];
void dfs(int x,int fa=0) {
    for(auto b:adj[x]) if(b!=fa) {
        dfs(b,x);
    }
    for(int o=0;o<2;++o)
    for(int fo=0;fo<2;++fo){
        ll&out=f[x][fo][o];
        vector<ll> ee;
        ll F=0;
        for(auto b:adj[x]) if(b!=fa) {
            F+=f[b][o][0];
            ee.push_back(f[b][o][1]-f[b][o][0]);
        }
        sort(ee.begin(),ee.end());
        reverse(ee.begin(),ee.end());
        for(int i=0;i<=ee.size();++i) {
            if(i) F+=ee[i-1];
            int c[2]={ee.size()-i,i};
            ll G=F;
            if(o==1) { //b
                G+=c[0]*(ll)(c[0]-1);
            }
            if(fa&&fo==0)
                G+=c[0]*2;
            out=max(out,G);
            if(!fa) ans=max(ans,G);
        }
    }
}
}
namespace ABB {
ll f[SZ][2][2];
void dfs(int x,int fa=0) {
    for(auto b:adj[x]) if(b!=fa) {
        dfs(b,x);
    }
    for(int o=0;o<2;++o)
    for(int fo=0;fo<2;++fo){
        ll&out=f[x][fo][o];
        vector<ll> ee;
        ll F=0;
        for(auto b:adj[x]) if(b!=fa) {
            F+=f[b][o][0];
            ee.push_back(f[b][o][1]-f[b][o][0]);
        }
        sort(ee.begin(),ee.end());
        reverse(ee.begin(),ee.end());
        for(int i=0;i<=ee.size();++i) {
            if(i) F+=ee[i-1];
            int c[2]={ee.size()-i,i};
            ll G=F;
            if(o==1) { //b
                G+=c[0]*(ll)c[1];
            }
            if(fa)
                G+=c[!fo];
            out=max(out,G);
            if(!fa) ans=max(ans,G);
        }
    }
}
}
namespace ABC {
ll f[SZ][2][2];
void dfs(int x,int fa=0) {
    for(auto b:adj[x]) if(b!=fa) {
        dfs(b,x);
    }
    for(int o=0;o<2;++o)
    for(int fo=0;fo<2;++fo){
        ll&out=f[x][fo][o];
        vector<ll> ee;
        ll F=0;
        for(auto b:adj[x]) if(b!=fa) {
            F+=f[b][o][0];
            ee.push_back(f[b][o][1]-f[b][o][0]);
        }
        sort(ee.begin(),ee.end());
        reverse(ee.begin(),ee.end());
        for(int i=0;i<=ee.size();++i) {
            if(i) F+=ee[i-1];
            int c[2]={ee.size()-i,i};
            ll G=F;
            if(fa&&!fo) c[0]++;
            if(o==1) { //b
                G+=(c[0]/2)*(ll)(c[0]-(c[0]/2));
            }
            out=max(out,G);
            if(!fa) ans=max(ans,G);
        }
    }
}
}
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(0);
    cin>>n>>w;
    for(int i=1,a,b;i<n;++i) {
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int dt=set<int>(w.begin(),w.end()).size();
    if(dt==1) {
        if(w.size()==1) ans=n;
        else if(w.size()==2) ans=2*(n-1);
        else {
            for(int i=1;i<=n;++i) {
                int d=adj[i].size();
                ans+=(ll)d*(d-1);
            }
        }
    }
    else if(w.size()==2) {
        AB::dfs(1);
    }
    else if(dt==3) {
        ABC::dfs(1);
    }
    else if(w[0]==w[2]) {
        ABA::dfs(1);
    }
    else {
        ABB::dfs(1);
    }
    cout<<ans<<"\n";
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5660kb

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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

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

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

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

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: -100
Wrong Answer
time: 1ms
memory: 3468kb

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:

61

result:

wrong answer 1st numbers differ - expected: '54', found: '61'
English 繁體中文 简体中文

服务器时间: 2024-12-12 06:21:14 | 开源项目