#include <bits/stdc++.h>
using namespace std;
int ind=0;
int t [500010];
vector <int> g [500010]; int n=0; int maxi=0;
void rec (string s, int i, int par){
maxi=max (maxi, i);
//cout << i << endl;
if (s [i]=='?'){
t [ind]=2;
g [par].push_back (ind);
ind++; n++;
}
if (s [i+1]=='i'){
t [ind]=0;
g [par].push_back (ind);
ind++;
rec (s, i+4, ind-1);
}
if (s [i+1]=='a'){
t [ind]=1;
g [par].push_back (ind);
ind++;
rec (s, i+4, ind-1);
}
i=maxi;
while (s [i]!=',') i++;
i++;
maxi=max (maxi, i);
if (s [i]=='?'){
t [ind]=2;
g [par].push_back (ind);
ind++; n++;
}
if (s [i+1]=='i'){
t [ind]=0;
g [par].push_back (ind);
ind++;
rec (s, i+4, ind-1);
}
if (s [i+1]=='a'){
t [ind]=1;
g [par].push_back (ind);
ind++;
rec (s, i+4, ind-1);
}
}
pair <int, int> sol (int x){
//cout << x << " " << t [x] << " ";
if (t [x]==2) return {1, n};
if (t [x]==1) return {sol (g[x][0]).first+sol (g[x][1]).first, max (sol (g[x][0]).second, sol (g[x][1]).second)};
return {min (sol (g[x][0]).first, sol (g[x][1]).first), sol (g[x][0]).second+sol (g[x][1]).second-n-1};
}
int main(){
string s; cin >> s;
rec (s, 0, 500000);
cout << sol (0).second-sol (0).first+1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
