이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int ind=0;
int t [5000010];
vector <int> g [5000010]; 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){
if (t [x]==2) return {1, n};
int l1=sol (g[x][0]).first; int l2=sol (g[x][1]).first; int r1=sol (g[x][0]).second; int r2=sol (g[x][1]).second;
if (t [x]==1) return {l1+l2, max (r1, r2)};
return {min (l1, l2), r1+r2-n-1};
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s; cin >> s;
rec (s, 0, 5000001);
//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... |