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<bits/stdc++.h>
using namespace std;
int type[1000005];
string s;
struct node{
int st,en,sz;
node(int _st=0,int _en=0,int _sz=0){
st=_st,en=_en,sz=_sz;
}
friend node operator+(node a,node b){
node c;
c.st=a.st+b.st;
c.en=max(a.en+b.sz,b.en+a.sz);
c.sz=a.sz+b.sz;
return c;
}
friend node operator-(node a,node b){
node c;
c.st=min(a.st,b.st);
c.en=a.en+b.en-1;
c.sz=a.sz+b.sz;
return c;
}
}info[10000005];
int cur=0;
int dfs(int u,int st){
if(s[st]=='?'){
info[u]=node(1,1,1);
//cerr<<u<<":leaf\n";
//cerr<<"vals:"<<info[u].st<<" "<<info[u].en<<" "<<info[u].sz<<"\n";
return st;
}else if(s[st+1]=='i'){
int id1=cur+1;
int st1=st+4;
int en1=dfs(++cur,st1);
int id2=cur+1;
int st2=en1+2;
int en2=dfs(++cur,st2);
info[u]=info[id1]-info[id2];
//cerr<<u<<":"<<id1<<" "<<id2<<"\n";
//cerr<<"vals:"<<info[u].st<<" "<<info[u].en<<" "<<info[u].sz<<"\n";
return en2+1;
}else{
int id1=cur+1;
int st1=st+4;
int en1=dfs(++cur,st1);
int id2=cur+1;
int st2=en1+2;
int en2=dfs(++cur,st2);
info[u]=info[id1]+info[id2];
//cerr<<u<<":"<<id1<<" "<<id2<<"\n";
//cerr<<"vals:"<<info[u].st<<" "<<info[u].en<<" "<<info[u].sz<<"\n";
return en2+1;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>s;
dfs(++cur,0);
cout<<info[1].en-info[1].st+1;
}
# | 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... |