Submission #784636

#	Time	Username	Problem	Language	Result	Execution time	Memory
784636		boris_mihov	Homework (CEOI22_homework)	C++17	100 / 100	526 ms	447612 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXLEN = 10000000;
const int MAXN = 10000000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

char s[MAXN];
int type[MAXN];
int dpMIN[MAXN][3];
int dpMAX[MAXN][3];
bool blMIN[MAXN][3];
bool blMAX[MAXN][3];
std::vector <int> g[MAXN];
std::stack <int> st;
int next[MAXN];
int end[MAXN];
int cnt;
int n;

int buildTree(int l, int r)
{
    if (l == r)
    {
        return ++cnt;
    }

    int node = ++cnt;
    if (s[l + 1] == 'i') type[node] = 1;
    else if (s[l + 1] == 'a') type[node] = 2;
    else assert(false);

    g[node].push_back(buildTree(l + 4, next[l + 3] - 1));
    g[node].push_back(buildTree(next[l + 3] + 1, end[l + 3] - 1));
    return node;
}

int fMIN(int node, int asked)
{
    if (g[node].empty())
    {
        if (asked == 0) return 1;
        return 0;
    }

    if (blMIN[node][asked])
    {
        return dpMIN[node][asked];
    }

    blMIN[node][asked] = true;
    dpMIN[node][asked] = INTINF;
    if (asked == 0)
    {
        if (type[node] == 1)
        {
            dpMIN[node][asked] = std::min(fMIN(g[node][0], 0), fMIN(g[node][1], 0));
        } else
        {
            dpMIN[node][asked] = fMIN(g[node][0], 0) + fMIN(g[node][1], 0);
        }
    } else if (asked == 1)
    {
        if (type[node] == 1)
        {
            dpMIN[node][asked] = std::min(dpMIN[node][asked], fMIN(g[node][0], 1) + fMIN(g[node][1], 2));
            dpMIN[node][asked] = std::min(dpMIN[node][asked], fMIN(g[node][0], 2) + fMIN(g[node][1], 1));
        } else
        {
            dpMIN[node][asked] = std::min(dpMIN[node][asked], fMIN(g[node][0], 1) + fMIN(g[node][1], 0));
            dpMIN[node][asked] = std::min(dpMIN[node][asked], fMIN(g[node][0], 0) + fMIN(g[node][1], 1));
        }
    } else
    {
        if (type[node] == 2)
        {
            dpMIN[node][asked] = std::min(fMIN(g[node][0], 2), fMIN(g[node][1], 2));
        } else
        {
            dpMIN[node][asked] = fMIN(g[node][0], 2) + fMIN(g[node][1], 2);
        }
    }

    return dpMIN[node][asked];
}

int fMAX(int node, int asked)
{
    if (g[node].empty())
    {
        if (asked == 0) return 1;
        return 0;
    }

    if (blMAX[node][asked])
    {
        return dpMAX[node][asked];
    }

    blMAX[node][asked] = true;
    dpMAX[node][asked] = -INTINF;
    if (asked == 0)
    {
        if (type[node] == 1)
        {
            dpMAX[node][asked] = std::max(fMAX(g[node][0], 0) + std::max(fMAX(g[node][1], 0), fMAX(g[node][1], 2)), std::max(fMAX(g[node][0], 0), fMAX(g[node][0], 2)) + fMAX(g[node][1], 0));
        } else
        {
            dpMAX[node][asked] = fMAX(g[node][0], 0) + fMAX(g[node][1], 0);
        }
    } else if (asked == 1)
    {
        if (type[node] == 1)
        {
            dpMAX[node][asked] = std::max(dpMAX[node][asked], fMAX(g[node][0], 1) + fMAX(g[node][1], 2));
            dpMAX[node][asked] = std::max(dpMAX[node][asked], fMAX(g[node][0], 2) + fMAX(g[node][1], 1));
        } else
        {
            dpMAX[node][asked] = std::max(dpMAX[node][asked], fMAX(g[node][0], 1) + fMAX(g[node][1], 0));
            dpMAX[node][asked] = std::max(dpMAX[node][asked], fMAX(g[node][0], 0) + fMAX(g[node][1], 1));
        }
    } else
    {
        if (type[node] == 2)
        {
            dpMAX[node][asked] = std::max(fMAX(g[node][0], 2) + std::max(fMAX(g[node][1], 0), fMAX(g[node][1], 2)), std::max(fMAX(g[node][0], 0), fMAX(g[node][0], 2)) + fMAX(g[node][1], 2));
        } else
        {
            dpMAX[node][asked] = fMAX(g[node][0], 2) + fMAX(g[node][1], 2);
        }
    }

    return dpMAX[node][asked];
}

void solve()
{
    int len = strlen(s + 1);
    for (int i = 1 ; i <= len ; ++i)
    {
        if (s[i] == '(') st.push(i);
        if (s[i] == ',')
        {
            next[st.top()] = i;
            st.pop();
        }
    }

    while (!st.empty())
    {
        st.pop();
    }

    for (int i = 1 ; i <= len ; ++i)
    {
        if (s[i] == '(') st.push(i);
        if (s[i] == ')')
        {
            end[st.top()] = i;
            st.pop();
        }
    }

    buildTree(1, len);
    n = cnt;

    // std::cout << "type\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cout << type[i] << '\n';
    // }

    // std::cout << "tree\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     for (const int &u : g[i])
    //     {
    //         std::cout << i << ' ' << u << '\n';
    //     }
    // }

    std::cout << fMAX(1, 1) - fMIN(1, 1) + 1 << '\n';
}

void input()
{
    std::cin >> s + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void input()':
Main.cpp:194:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |     std::cin >> s + 1;
      |                 ~~^~~

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