제출 #1307099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307099		simona1230	Homework (CEOI22_homework)	C++20	100 / 100	198 ms	170016 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn=2*1e6+5;
string s;
int a[maxn];
vector<int> v[maxn];
int num=0,g;
void build()
{
    stack<int> h;
    for(int i=0;i<s.size();i++)
    {
        int tp=0;
        if(s[i]=='m')
        {
            if(s[i+1]=='i')a[++num]=-1;
            else a[++num]=1;

            if(h.size())
                v[h.top()].push_back(num);
            h.push(num);
        }

        if(s[i]==')')
            h.pop();

        if(s[i]=='?')
        {
            num++;
            g++;
            v[h.top()].push_back(num);
        }
    }

    /*for(int i=1;i<=num;i++)
    {
        cout<<i<<":: ";
        for(auto j:v[i])
            cout<<j<<" ";
                cout<<endl;
    }*/
}

int cnt[maxn];
int l[maxn],r[maxn];

void dfs(int i)
{
    for(auto j:v[i])
    {
        dfs(j);
        cnt[i]+=cnt[j];
    }

    if(v[i].size())
    {
        int v1=v[i][0];
        int v2=v[i][1];

        if(a[i]==1)
        {
            l[i]=l[v1]+l[v2];
            r[i]=cnt[v1]+cnt[v2]-min(cnt[v1]-r[v1],cnt[v2]-r[v2]);
        }
        else
        {
            l[i]=min(l[v1],l[v2]);
            r[i]=r[v1]+r[v2]-1;
        }
    }
    else
    {
        cnt[i]=1;
        l[i]=1;
        r[i]=1;
    }
}

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

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