Submission #845019

#	Time	Username	Problem	Language	Result	Execution time	Memory
845019		kderylo	Homework (CEOI22_homework)	C++17	100 / 100	370 ms	220388 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
const int stala=3e6+10;
vector<int>w[stala];
int dp[stala][2];
int tab[stala]; //0-? 1-min 2-max
int index=0,l=0;
string s;
void make_edge(int x,int y)
{
    if(x==-1||y==-1){
        return;
    }
    w[x].push_back(y);
    w[y].push_back(x);
}
int f(int pop,int start)
{
    index++;
    make_edge(pop,index);
    int current_index=index;
    if(s[start]=='?'){
        l++;
        return start;
    }
    else if(s[start+1]=='i'){
        tab[current_index]=1;
        int pom=f(current_index,start+4)+2;
        return f(current_index,pom)+1;
    }
    else{
        tab[current_index]=2;
        int pom=f(current_index,start+4)+2;
        return f(current_index,pom)+1;
    }
}
void dfs(int k)
{
    if(tab[k]==0){
        dp[k][0]=1;
        dp[k][1]=1;
    }
    else if(k==1){
        dfs(w[k][0]);
        dfs(w[k][1]);
        int a1=dp[w[k][0]][0];
        int b1=dp[w[k][1]][0];
        int a2=dp[w[k][0]][1];
        int b2=dp[w[k][1]][1];
        if(tab[k]==1){
            dp[k][0]=min(a1,b1);
            dp[k][1]=a2+b2;
        }
        else{
            dp[k][0]=a1+b1;
            dp[k][1]=min(a2,b2);
        }
    }
    else{
        dfs(w[k][1]);
        dfs(w[k][2]);
        int a1=dp[w[k][1]][0];
        int b1=dp[w[k][2]][0];
        int a2=dp[w[k][1]][1];
        int b2=dp[w[k][2]][1];
        if(tab[k]==1){
            dp[k][0]=min(a1,b1);
            dp[k][1]=a2+b2;
        }
        else{
            dp[k][0]=a1+b1;
            dp[k][1]=min(a2,b2);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    f(-1,0);
    dfs(1);
    int x=dp[1][0];
    int y=l-dp[1][1]+1;
    cout<<max(0,y-x+1);

    return 0;
}

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