1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#define MAXN 10150UL
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct Node{
int fa,sd,id,son[3];
}op[MAXN];
int cnt,p,maxn[MAXN][3],minn[MAXN][3];
int maxans=0,minans=505290270;
string s;
int MIN(int a,int b){
if(a<b) return a;
else return b;
}
int MAX(int a,int b){
if(a<b) return b;
else return a;
}
void dfs(int x){
// printf("%d\n",p);
op[++cnt].fa=x;
if(op[x].son[1]) op[x].son[2]=cnt;
else op[x].son[1]=cnt;
op[cnt].id=cnt;
op[cnt].sd=s[p]-'0';
int os=cnt;
for(int i=1;i<=op[os].sd;i++){
p++;
dfs(os);
}
}
//green 0 red 1 blue 2
void dp(int x){
if(op[x].sd==0){
maxn[x][0]=1;
minn[x][0]=1;
minn[x][1]=0;
minn[x][2]=0;
return ;
}
for(int i=1;i<=op[x].sd;i++){
dp(op[x].son[i]);
}
if(op[x].sd==1){
int t=op[x].son[1];
maxn[x][0]=MAX(maxn[t][1],maxn[t][2])+1;
maxn[x][1]=MAX(maxn[t][0],maxn[t][2]);
maxn[x][2]=MAX(maxn[t][0],maxn[t][1]);
minn[x][0]=MIN(minn[t][1],minn[t][2])+1;
minn[x][1]=MIN(minn[t][0],minn[t][2]);
minn[x][2]=MIN(minn[t][0],minn[t][1]);
}
else{
int t=op[x].son[1]; int k=op[x].son[2];
maxn[x][0]=MAX(maxn[t][1]+maxn[k][2],maxn[t][2]+maxn[k][1])+1;
maxn[x][1]=MAX(maxn[t][0]+maxn[k][2],maxn[t][2]+maxn[k][0]);
maxn[x][2]=MAX(maxn[t][0]+maxn[k][1],maxn[t][1]+maxn[k][0]);
minn[x][0]=MIN(minn[t][1]+minn[k][2],minn[t][2]+minn[k][1])+1;
minn[x][1]=MIN(minn[t][0]+minn[k][2],minn[t][2]+minn[k][0]);
minn[x][2]=MIN(minn[t][0]+minn[k][1],minn[t][1]+minn[k][0]);
}
}
int main(){
/* freopen("trot.in","r",stdin);
freopen("trot.ans","w",stdout);*/
cin>>s;
dfs(0);
/* for(int i=1;i<=cnt;i++){
printf("%d\n",op[i].sd);
}*/
memset(minn,30,sizeof(minn));
dp(1);
/* for(int i=1;i<=cnt;i++)
printf("%d %d %d\n",minn[i][0],minn[i][1],minn[i][2]);*/
printf("%d %d",MAX(MAX(maxn[1][0],maxn[1][1]),maxn[1][2]),MIN(MIN(minn[1][0],minn[1][1]),minn[1][2]));
}
|
