Submission #968499

#	Time	Username	Problem	Language	Result	Execution time	Memory
968499		anton	Homework (CEOI22_homework)	C++17	100 / 100	203 ms	189356 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

const int MAX_N = 1000000;
vector<int> ch[2*MAX_N];
vector<int> tp;
vector<int> sz;
//0 = ?, 1 = min 2 = max

string s;
int parse(int anc, int lt,  int t){

    if(anc != -1){
        ch[anc].push_back(t);
    }
    
    sz.push_back(0);
    
    if(s[lt] == '?'){
        tp.push_back(0);
        
        sz[t] =1;
        return lt+1;
    }
    else{

        if(s[lt+1]== 'i'){
            tp.push_back(1);
        }
        else{
            tp.push_back(2);
        }
    }

    int mid =parse(t, lt+4, t+1);
    int lid = tp.size();
    int last= parse(t, mid+1, tp.size());
    sz[t]  =sz[t+1] + sz[lid];
    /*cout<<t<<" ";
    for(int i = lt; i<last+1; i++){
        cout<<s[i];
    }
    cout<<endl;*/
    return last+1;
    
}

pii find_inter(int id){
    pii res;
    if(tp[id] == 0){
        res=  {0, 0};
    }
    else{
        pii lh = find_inter(ch[id][0]);
        int lid = ch[id][0];
        pii rh = find_inter(ch[id][1]);
        int rid = ch[id][1];

        if(tp[id] ==1){
            res = {min(lh.first, rh.first), lh.second+rh.second};
        }
        else{

            res = {lh.first+rh.first+1, sz[id]-1-min(sz[lid]-lh.second-1, sz[rid]-rh.second-1)};
        }
    }
    //cout<<id<<" "<<res.first<<" "<<res.second<<endl;
    return res;
}

signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);    

    cin>>s;
    int ended_at =parse(-1, 0,0);
    
    pii res =find_inter(0);
    
    cout<<res.second-res.first+1<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:79:9: warning: unused variable 'ended_at' [-Wunused-variable]
   79 |     int ended_at =parse(-1, 0,0);
      |         ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34