QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471638#8213. GraffitiPhantomThresholdWA 3ms12196kbC++174.7kb2024-07-10 23:56:502024-07-10 23:56:51

Judging History

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

  • [2024-07-10 23:56:51]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：12196kb
查看
  • [2024-07-10 23:56:50]
  • 提交

answer

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

typedef long long ll;
const ll INF=1e18;
const int maxn=300000;
int n;
string str;
int __TP=-1;

vector<int> g[maxn+50];
ll dp[maxn+50][2][2];

inline void upd(ll &A,ll B){if (A<=B) A=B;}

void dfs(int u,int fa){
	int sz=0;
	for (auto v:g[u]){
		if (v==fa) continue;
		sz++;
		dfs(v,u);
	}
	if (sz==0){
		for (int j=0;j<=1;j++){
			for (int k=0;k<=1;k++){
				dp[u][j][k]=0;
			}
		}
		return;
	}
	if (__TP==0){
		// abb
		{
			// ?aa && ?ab
			ll base=0;
			for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
			dp[u][0][0]=dp[u][0][1]=base;
		}
		{
			//?ba
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1])-(dp[v][1][1]+1));
				base+=(dp[v][1][1]+1);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][0]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][0],base+presum+i*(sz-i));
			}
		}
		{
			//?bb
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1]+1)-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][1]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][1],base+presum+i*(sz-i));
			}	
		}
	}
	else if (__TP==1){
		//aba
		{
			// ?aa && ?ab
			ll base=0;
			for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
			dp[u][0][0]=dp[u][0][1]=base;
		}
		{
			//?ba
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1]+1)-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][0]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][0],base+presum+i*(i-1)/2);
			}	
		}
		{
			//?bb
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][1]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][1],base+presum+i*(i-1)/2);
			}	
		}
	}
	else{
		//abc
		{
			// ?aa && ?ab
			ll base=0;
			for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
			dp[u][0][0]=dp[u][0][1]=base;
		}
		{
			//?ba
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][0]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][0],base+presum+((i+1)/2)*(i+1-(i+1)/2));
			}
		}
		{
			//?bb
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=fa){
				tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp[u][1][1]=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp[u][1][1],base+presum+(i/2)*(i-i/2));
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n;
	cin >> str;
	for (int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	if (str.size()==1){
		cout << n << "\n";
		return 0;	
	}
	if (str.size()==2){
		if (str[0]!=str[1]) cout << n-1 << "\n";
		else cout << 2*(n-1) << "\n";
		return 0;	
	}
	if (str[0]==str[1] && str[1]==str[2]){
		long long sum=0;
		for (int i=1;i<=n;i++){
			long long sz=g[i].size();
			sum=sum+sz*(sz-1)/2;
		}
		cout << 2*sum << "\n";
		return 0;
	}
	if (str[0]==str[1]) __TP=0,str="abb";
	else if (str[0]==str[2]) __TP=1,str="aba";
	else __TP=2,str="abc";
	
	for (int i=0;i<=n;i++){
		for (int j=0;j<=1;j++){
			for (int k=0;k<=1;k++){
				dp[i][j][k]=-INF;	
			}
		}
	}
	dfs(1,0);
	ll ans=0;
	if (__TP==0){
		//abb
		ans=max(ans,dp[1][0][0]);
		ans=max(ans,dp[1][0][1]);
		{
			//?bb
			int u=1;
			int sz=g[1].size();
			ll dp1=0;
			vector<ll> tmp;
			ll base=0;
			for (auto v:g[u]) if (v!=0){
				tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
				base+=(dp[v][1][1]);
			}
			sort(tmp.begin(),tmp.end(),greater<ll>());
			
			dp1=base;
			ll presum=0;
			for (ll i=1;i<=sz;i++){
				presum=presum+tmp[i-1];
				upd(dp1,base+presum+i*(sz-i));
			}
			ans=max(ans,dp1);
		}
	}
	else if (__TP==1){
		//aba
		ans=max(ans,2*dp[1][0][0]);
		ans=max(ans,2*dp[1][0][1]);
		ans=max(ans,2*dp[1][1][1]);
	}
	else{
		//abc
		ans=max(ans,dp[1][0][0]);
		ans=max(ans,dp[1][0][1]);
		ans=max(ans,dp[1][1][1]);	
	}
	cout << ans << "\n";
	return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 11560kb

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 11204kb

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 2ms
memory: 11356kb

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

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: 2ms
memory: 12196kb

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

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

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: 2ms
memory: 11552kb

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

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: 0ms
memory: 11188kb

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:

35

result:

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

伺服器時間: 2024-12-12 06:26:56 | 開源專案