Submission #1174279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174279		heeheeheehaaw	Homework (CEOI22_homework)	C++20	0 / 100	186 ms	169648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int parent[2000005];
int tip[2000005];
int hei, cnt, n;
vector<int> adj[2000005];
int cdr, siz[2000005];

void dfs(int nod, int nr = 0)
{
    if(tip[nod] == 0) siz[nod] = 1, nr++;
    for(auto it : adj[nod])
    {
        dfs(it, nr);
        siz[nod] += siz[it];
    }
    if(tip[nod] == 0) nr--;
    if(nr == 0)
        cdr = max(cdr, n - siz[nod]);
}



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

    string s;
    cin>>s;

    bool swapped = false;
    if(s[1] == 'i')
        swapped = true;

    hei = 0;
    cnt++, tip[cnt] = 0;
    if(!swapped) tip[cnt] = 1;

    int currnod = 1;
    parent[1] = 1;
    for(int i = 3; i < s.size(); i++)
    {
        if(s[i] == '(')
        {
            hei++;
        }
        else if(s[i] == ')')
        {
            hei--;
            currnod = parent[currnod];
        }
        else if(s[i] == ',')
        {
            hei--;
            currnod = parent[currnod];
        }
        else if(s[i] == '?')
        {
            hei++;
            adj[currnod].push_back(++cnt);
            tip[cnt] = 2;
            parent[cnt] = currnod;
            currnod = cnt;
        }
        else
        {
            i++, cnt++;
            hei++;
            if(s[i] == 'i')
            {
                adj[currnod].push_back(cnt);
                parent[cnt] = currnod;
                tip[cnt] = 0;
                currnod = cnt;
            }
            else
            {
                adj[currnod].push_back(cnt);
                parent[cnt] = currnod;
                tip[cnt] = 1;
                currnod = cnt;
            }

            i++;
        }
    }

    if(swapped)
        for(int i = 1; i <= cnt; i++)
            if(tip[i] < 2)
                tip[i] = 1 - tip[i];

    /*for(int i = 1; i <= cnt; i++)
    {
        cout<<"nodul "<<i<<" de tip "<<tip[i]<<'\n';
        for(auto it : adj[i])
            cout<<it<<" ";
        cout<<'\n';
    }*/

    int cst = 0;
    for(int i = 1; i <= cnt; i++)
    {
        if(tip[i] == 0)
            cst++;
        else if(tip[i] == 2)
            n++;
    }

    cst = n - cst;
    cdr = cst;
    dfs(1);
    /*cout<<cst<<" "<<cdr<<" "<<n<<"\n";*/
    cout<<cdr - cst + 1;
    return 0;
}

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