이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int ind=0;
int t [2000010];
vector <int> g [2000010]; 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);
}
if (i==0) return ;
i=maxi;
//cout << maxi << endl;
while (s [i]!=',') i++;
i++;
//cout << i << " " << ind << endl;
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);
}
return ;
}
pair <int, int> sol (int x){
//cout << 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, 2000001);
//cout << g [0].size();
cout << sol (0).second-sol (0).first+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... |