This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stack>
using namespace std;
string s;
int cnt, n;
#define nmax 4000001
int lSon[nmax], rSon[nmax], parent[nmax], arb[nmax], minn[nmax], maxx[nmax], sizee[nmax];
// 0 - frunza, 1 - maxim, -1 - minim
int is_min( int i ) {
if( s[i] == 'm' && s[i + 1] == 'i' && s[i + 2] == 'n' )
return 1;
return 0;
}
int is_max( int i ) {
if( s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'x' )
return 1;
return 0;
}
void init( int l, int vf ) {
if( l >= n )
return;
//cout << l << " " << vf << "\n";
if( is_min( l ) ) {
arb[vf] = -1;
cnt++;
lSon[vf] = cnt;
parent[cnt] = vf;
init( l + 4, cnt );
} else if( is_max( l ) ) {
arb[vf] = 1;
cnt++;
lSon[vf] = cnt;
parent[cnt] = vf;
init( l + 4, cnt );
} else if( s[l] == ',' ) {
cnt++;
parent[cnt] = parent[vf];
rSon[parent[vf]] = cnt;
init( l + 1, cnt );
} else if( s[l] == ')' ) {
init( l + 1, parent[vf] );
} else {
init( l + 1, vf );
}
}
void dfs( int vf ) {
if( arb[vf] == 0 ) {
sizee[vf] = 1;
minn[vf] = maxx[vf] = 1;
//cout << vf << " " << arb[vf];
//cout << "\n";
return;
}
dfs( lSon[vf] );
dfs( rSon[vf] );
sizee[vf] = sizee[lSon[vf]] + sizee[rSon[vf]];
if( arb[vf] == -1 ) {
minn[vf] = min( minn[lSon[vf]], minn[rSon[vf]] );
maxx[vf] = maxx[lSon[vf]] + maxx[rSon[vf]] - 1;
} else {
minn[vf] = minn[lSon[vf]] + minn[rSon[vf]];
maxx[vf] = max( sizee[lSon[vf]] + maxx[rSon[vf]], sizee[rSon[vf]] + maxx[lSon[vf]] );
}
//cout << vf << " " << arb[vf] << " ";
//cout << maxx[vf] << " " << minn[vf] << " " << sizee[vf] << "\n";
}
int main() {
cin >> s;
n = s.size();
cnt = 1;
init( 0, 1 );
dfs( 1 );
cout << 1 - minn[1] + maxx[1];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |