Submission #1254352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254352		Jovica	Homework (CEOI22_homework)	C++20	100 / 100	164 ms	137640 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e6+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 (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;
}

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