Submission #991095

#	Time	Username	Problem	Language	Result	Execution time	Memory
991095		andrei_iorgulescu	Homework (CEOI22_homework)	C++14	100 / 100	71 ms	102096 KiB

Main

#include <bits/stdc++.h>

using namespace std;

string a;
int poz;
int curnod = 1;
int l[4000005],r[4000005],s[4000005];
int fs[4000005],fd[4000005],tip[4000005];

void build_tree(int nod)
{
    if (a[poz] != '?')
    {
        if (a[poz + 1] == 'i')
            tip[nod] = 0;
        else
            tip[nod] = 1;
        poz += 4;
        curnod++;
        fs[nod] = curnod;
        build_tree(curnod);
        poz++;
        curnod++;
        fd[nod] = curnod;
        build_tree(curnod);
        poz++;
    }
    else
    {
        tip[nod] = -1;
        fs[nod] = fd[nod] = -1;
        poz++;
    }
}

void dfs(int nod)
{
    if (fs[nod] == -1)
        l[nod] = r[nod] = s[nod] = 1;
    else
    {
        dfs(fs[nod]);
        dfs(fd[nod]);
        s[nod] = s[fs[nod]] + s[fd[nod]];
        if (tip[nod] == 0)
        {
            l[nod] = min(l[fs[nod]],l[fd[nod]]);
            r[nod] = r[fs[nod]] + r[fd[nod]] - 1;
        }
        else
        {
            l[nod] = l[fs[nod]] + l[fd[nod]];
            r[nod] = max(r[fs[nod]] + s[fd[nod]],r[fd[nod]] + s[fs[nod]]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a;
    build_tree(1);
    dfs(1);
    cout << r[1] - l[1] + 1;
    return 0;
}

/**
Construiesc arborele ala
Fiecare nod poate avea un interval
Daca e frunza, e L = R = S = 1
Fie L1 R1 S1 si L2 R2 S2 L,R si size-ul pentru fii
S = S1 + S2 oricum
Daca e nod de min, L = min(L1,L2), R = R1 + R2 - 1
Daca e nod de max, L = L1 + L2 + 1, R = max(L1 + S2,L2 + S1)
**/

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