QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320427#8213. Graffitiucup-team052#RE 165ms41788kbC++234.5kb2024-02-03 16:41:062024-02-03 16:41:06

Judging History

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

  • [2024-02-03 16:41:06]
  • 评测
  • 测评结果:RE
  • 用时:165ms
  • 内存:41788kb
  • [2024-02-03 16:41:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 300005
char _str[5];
int str[3],m;
vector<int> G[N];
int n;
ll f[N][3][3],g[N][3],w12[N],w[N];
int a[N],b[N],dpos[N],reva[N];
vector<int> d[N];
ll solve(int n)
{
	// for(int i=0;i<n;i++) printf("%d%c",g[i][0]," \n"[i==n-1]);
	// for(int i=0;i<n;i++) printf("%d%c",g[i][1]," \n"[i==n-1]);
	// for(int i=0;i<n;i++) printf("%d%c",g[i][2]," \n"[i==n-1]);
	for(int i=0;i<=n;i++) w12[i]=0;
	for(int i=0;i<n;i++)
	{
		int dpos=g[i][1]-g[i][2];
		dpos=min(dpos,n+1);
		dpos=max(dpos,0);
		w[i]=g[i][0]-max(g[i][1],g[i][2]);
		w12[dpos+1]++;
		::dpos[i]=dpos;
		d[dpos].push_back(i);
	}
	for(int i=1;i<=n;i++) w12[i]+=w12[i-1];
	for(int i=0;i<n;i++) w12[0]+=max(g[i][1],g[i][2]);
	for(int i=1;i<=n;i++) w12[i]+=w12[i-1];
	for(int i=1;i<=n;i++) a[i]=b[i]=i-1;
	sort(a+1,a+n+1,[&](int x,int y){
		return w[x]>w[y];
	});
	for(int i=1;i<=n;i++) reva[a[i]]=i;
	sort(b+1,b+n+1,[&](int x,int y){
		return w[x]+dpos[x]>w[y]+dpos[y];
	});
	ll ans=w12[0]; int posa=0,posb=0,inb=0;
	auto gval=[&](int i,int u)
	{
		if(i<=dpos[u]) return w[u];
		else return w[u]-(i-dpos[u]);
	};
	// for(int i=0;i<=n;i++) printf("%d%c",w12[i]," \n"[i==n]);
	// for(int i=0;i<n;i++) printf("%d %d\n",w[i],dpos[i]);
	ll suma=0;
	for(int i=1;i<=n;i++)
	{
		while(posb>=1&&posa<n&&gval(i,b[posb])<gval(i,a[posa+1]))
		{
			if(dpos[b[posb]]<i) assert(0);
			else if(dpos[a[posa+1]]>i) posa++;
			else
			{
				posb--,inb--,posa++;
				suma++;
			}
		}
		suma-=inb;
		while(posb<n&&dpos[b[posb+1]]>i) posb++;
		while(posa<n&&dpos[a[posa+1]]<i) posa++;
		if(posb<n&&(posa==n||gval(i,b[posb+1])>gval(i,a[posa+1])))
		{
			// printf("b : %d\n",b[posb+1]);
			inb++; posb++;
			suma+=gval(i,b[posb]);
		}
		else
		{
			// printf("a : %d * %d\n",a[posa+1],gval(i,a[posa+1]));
			posa++;
			suma+=gval(i,a[posa]);
		}
		// printf("* %d : %d\n",i,suma);
		ans=max(ans,w12[i]+suma);
		for(int j:d[i]) if(reva[j]<=posa) inb++;
	}
	for(int i=0;i<=n+1;i++) d[i].clear();
	return ans;
}
void dfs(int u,int fa)
{
	for(int v:G[u]) if(v!=fa) dfs(v,u);
	for(int c=0;c<m;c++) for(int d=0;d<m;d++)
	{
		if(u==1) d=m;
		if(str[1]==c)
		{
			vector<ll> tw[m];
			for(int v:G[u]) if(v!=fa) for(int j=0;j<m;j++) tw[j].push_back(f[v][j][c]);
			for(int j=0;j<m;j++)
			{
				if(str[0]==j&&str[2]==d) for(int i=0;i<(int)tw[j].size();i++) tw[j][i]++;
				if(str[0]==d&&str[2]==j) for(int i=0;i<(int)tw[j].size();i++) tw[j][i]++;
			}
			ll ans=0;
			if(str[0]==str[2])
			{
				if(m==1)
				{
					ans=1LL*(int)tw[0].size()*((int)tw[0].size()-1);
					for(int i=0;i<(int)tw[0].size();i++) ans+=tw[0][i];
				}
				else
				{
					priority_queue<ll> q;
					ll cur=0;
					for(int i=0;i<(int)tw[0].size();i++) q.push(tw[0][i]-tw[1][i]),cur+=tw[1][i];
					ans=cur;
					for(int i=1;i<=(int)tw[0].size();i++)
					{
						cur+=q.top(); q.pop();
						ans=max(ans,cur+1LL*i*(i-1));
					}
				}
			}
			else
			{
				for(int j=0;j<3;j++)
				{
					for(int i=0;i<(int)tw[0].size();i++) g[i][j]=tw[str[j]][i];
				}
				ans=solve(tw[0].size());
			}
			f[u][c][min(d,m-1)]=ans;
		}
		else
		{
			ll w=0;
			for(int v:G[u]) if(v!=fa)
			{
				ll mx=0;
				for(int j=0;j<m;j++) mx=max(mx,f[v][j][c]);
				w+=mx;
			}
			f[u][c][min(d,m-1)]=w;
		}
	}
	// printf("%d :\n",u);
	// for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",f[u][i][j]," \n"[j==m-1]);
}
signed main()
{
	cin>>n; scanf("%s",_str);
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		G[u].pb(v),G[v].pb(u);
	}
	if(strlen(_str)==1) cout<<n<<endl,exit(0);
	if(strlen(_str)==2)
	{
		ll ans=0;
		for(int i=1;i<=n;i++) ans+=G[i].size();
		if(_str[0]==_str[1]) cout<<ans<<endl;
		else cout<<ans/2<<endl;
		return 0;
	}
	for(int i=0;i<3;i++)
	{
		int ok=0;
		for(int j=0;j<i;j++) if(_str[i]==_str[j]) str[i]=str[j],ok=1;
		if(!ok) str[i]=m++;
	}
	dfs(1,0);
	ll ans=0;
	for(int c=0;c<m;c++) ans=max(ans,f[1][c][m-1]);
	cout<<ans<<endl;
	return 0;
}



詳細信息

Test #1:

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

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 44ms
memory: 20464kb

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: 0
Accepted
time: 51ms
memory: 20464kb

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:

599998

result:

ok 1 number(s): "599998"

Test #23:

score: 0
Accepted
time: 16ms
memory: 10496kb

input:

123234
ab
5333 65911
93667 3824
117784 113995
122335 34180
100563 13017
2356 55265
68248 30680
67326 55966
55450 2923
86794 12061
49667 54440
46800 106814
4840 7419
53069 122499
34188 99215
18873 90062
115319 82268
1093 52619
108703 107429
40381 14308
91251 53870
7680 94995
90630 57256
78084 11866
3...

output:

123233

result:

ok 1 number(s): "123233"

Test #24:

score: 0
Accepted
time: 98ms
memory: 41708kb

input:

300000
aaa
286864 6103
13963 130993
193857 266146
21588 192178
60950 206316
57174 172746
83177 159553
274512 266893
1479 82701
149984 220249
66444 38360
164961 269188
90561 160425
48372 223724
176008 89731
146829 119384
4625 131173
271552 74420
258647 63612
101816 202418
73996 284875
167169 62661
18...

output:

1202694

result:

ok 1 number(s): "1202694"

Test #25:

score: 0
Accepted
time: 156ms
memory: 41788kb

input:

300000
wow
33050 101378
38107 258970
169311 109231
147923 297962
291294 116868
35054 53343
198452 192697
213787 257591
188731 256973
281711 199138
234546 68112
204998 251624
97110 216134
250244 200876
285877 202008
173953 211734
40140 26823
71958 217939
219546 251422
128294 208345
55792 155
162308 2...

output:

691046

result:

ok 1 number(s): "691046"

Test #26:

score: 0
Accepted
time: 165ms
memory: 41732kb

input:

300000
bob
3546 155583
136408 83861
111087 14272
247003 298086
108933 172420
164224 266023
111269 244728
113434 88159
133416 293100
147988 29901
261668 83495
56261 94204
102384 32287
226850 127102
206891 175776
943 283177
269178 25048
239910 24108
129685 205836
12217 98902
256855 9020
289624 267084
...

output:

691252

result:

ok 1 number(s): "691252"

Test #27:

score: -100
Runtime Error

input:

300000
oop
262845 173800
283177 94631
297757 21360
86111 283443
104846 44242
146147 80602
172254 3094
18207 36330
116034 170256
241960 205186
70178 78225
70995 118475
205702 210175
286804 82561
5920 218263
217010 270658
109005 165733
173532 245803
234143 242996
183220 280923
42808 252787
103082 6893...

output:


result: