제출 #1254351

#제출 시각아이디문제언어결과실행 시간메모리
1254351JovicaHomework (CEOI22_homework)C++20
53 / 100
65 ms87956 KiB
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6+1;
struct Node{
    int levo=-1,desno=-1;
    bool b = false;
    int l=0,r=0;
};
vector<Node> drvo;
string s;
int pozicija;
int ss[maxn];

void izgradi()
{
    Node prazno;drvo.push_back(prazno);
    int p = drvo.size()-1;
    while (pozicija < s.size())
    {
        char c = s[pozicija];if (c == 'm' || c == 'i' || c == 'n' || c=='x') pozicija++;
        if (c == 'a') drvo[p].b = true,pozicija++;
        if (c == '?' || c == ')') {
            pozicija++;break;
        }
        if (c == '('){
            drvo[p].levo = drvo.size();
            pozicija++;
            izgradi();
        }
        if (c == ','){
            drvo[p].desno = drvo.size();
            pozicija++;
            izgradi();
        }
    }
    if (drvo[p].levo == -1) ss[p] = 1;
    else ss[p] = ss[drvo[p].levo]+ss[drvo[p].desno];
}
int n;

int vidi(int m)
{
    int k = 0;
    while (m%2==0){
        k++;m/=2;
    }

    return k;
}

void f(int p)
{
    if (ss[p] == 1) return;

    int l = drvo[p].levo,d = drvo[p].desno;
    f(l);f(d);
    if (drvo[p].b)
    {
        drvo[p].l = drvo[l].l + drvo[d].l + 1;
        drvo[p].r = min(drvo[l].r,drvo[d].r);
    }
    else
    {
        drvo[p].l = min(drvo[l].l,drvo[d].l);
        drvo[p].r = drvo[l].r + drvo[d].r + 1;
    }
}

int main()
{ios_base::sync_with_stdio(false);cin.tie();cout.tie(0);

    cin>>s;
    izgradi();

    //for(auto a: drvo) cout<<a.levo<<" "<<a.desno<<" "<<a.b<<endl;

    //for (int i=0;i<drvo.size();i++) cout<<ss[i]<<" ";cout<<endl;

    for (int i=0;i<drvo.size();i++) if (ss[i]==1) n++;


    f(0);
    cout<<n-drvo[0].r-drvo[0].l<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...