제출 #1229300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229300		alexander707070	Homework (CEOI22_homework)	C++20	100 / 100	111 ms	81800 KiB

Main

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

struct node{
    int l,r;
    int type;
};

int n;
string s;
stack<int> st;

node tree[MAXN];
int sum[MAXN];

void add_edge(int x,int y){
    if(tree[x].l==0)tree[x].l=y;
    else tree[x].r=y;
}

int dp[MAXN][2];

int ff(int x,int t){
    if(x==0)return 1;

    if(dp[x][t]>0)return dp[x][t];

    if(tree[x].type!=t){
        dp[x][t]=ff(tree[x].l,t) + ff(tree[x].r,t);
    }else{
        dp[x][t]=min(ff(tree[x].l,t) , ff(tree[x].r,t));
    }

    return dp[x][t];
}

int smaller,bigger;

void dfs(int x){

    if(x==0){
        sum[smaller+1]++;
        sum[n-bigger+1]--;
        return;
    }

    if(tree[x].type==1){
        smaller+=ff(tree[x].r,2);
        dfs(tree[x].l);
        smaller-=ff(tree[x].r,2);
        
        smaller+=ff(tree[x].l,2);
        dfs(tree[x].r);
        smaller-=ff(tree[x].l,2);
    }else{
        bigger+=ff(tree[x].r,1);
        dfs(tree[x].l);
        bigger-=ff(tree[x].r,1);
        
        bigger+=ff(tree[x].l,1);
        dfs(tree[x].r);
        bigger-=ff(tree[x].l,1);
    }

}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>s;
    st.push(0);

    for(int i=0;i<s.size();i++){
        if(s[i]=='m' or s[i]=='n' or s[i]=='(' or s[i]==',' or s[i]=='?')continue;

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

        if(s[i]=='a' or s[i]=='i'){

            n++;
            add_edge(st.top(),n);
            
            if(s[i]=='a')tree[n].type=1;
            else tree[n].type=2;

            st.push(n);
        }
    }

    n++;
    dfs(1);

    int s=0,ans=0;
    for(int i=1;i<=n;i++){
        s+=sum[i];
        if(s>0)ans++;
    }

    cout<<ans<<"\n";

    return 0;
}

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