제출 #683337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683337		Tenis0206	Homework (CEOI22_homework)	C++11	100 / 100	114 ms	119864 KiB

Main

#include <bits/stdc++.h>

using namespace std;

string s;

int tip[2000005], w[2000005];

int st[2000005],dr[2000005];

pair<int,int> dp[2000005];

int p = 0;

void dfs(int nod)
{
    if(tip[nod]==2)
    {
        dp[nod].first = 1;
        dp[nod].second = 1;
        w[nod] = 1;
        return;
    }
    dfs(st[nod]);
    w[nod] += w[st[nod]];
    dfs(dr[nod]);
    w[nod] += w[dr[nod]];
    if(tip[nod]==0)
    {
        dp[nod].first = min(dp[st[nod]].first,dp[dr[nod]].first);
        dp[nod].second = dp[st[nod]].second + dp[dr[nod]].second - 1;
    }
    else
    {
        dp[nod].first = dp[st[nod]].first + dp[dr[nod]].first;
        dp[nod].second = max(w[st[nod]] + dp[dr[nod]].second, w[dr[nod]] + dp[st[nod]].second);
    }
}

int nod = 1;

void eval()
{
    if(s[p]=='?')
    {
        tip[nod] = 2;
        ++p;
        return;
    }
    if(s[p+1]=='i')
    {
        tip[nod] = 0;
    }
    else
    {
        tip[nod] = 1;
    }
    p += 4;
    int c_nod = nod;
    st[c_nod] = (++nod);
    eval();
    ++p;
    dr[c_nod] = (++nod);
    eval();
    ++p;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    nod = 1;
    eval();
    dfs(1);
    cout<<dp[1].second - dp[1].first + 1<<'\n';
    return 0;
}

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