Submission #954265

#	Time	Username	Problem	Language	Result	Execution time	Memory
954265		LucaIlie	Homework (CEOI22_homework)	C++17	100 / 100	353 ms	139956 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e6;
string s;
int n;
int pos;
int type[MAX_N + 1], leftSon[MAX_N + 1], rightSon[MAX_N + 1], sz[MAX_N + 1], minn[MAX_N + 1], maxx[MAX_N + 1];

int buildTree() {
    n++;
    int v = n;

    if ( s[pos] == '?' ) {
        type[v] = 0;
        return v;
    }

    type[v] = (s[pos + 1] == 'i' ? 1 : 2);
    pos += 4;
    leftSon[v] = buildTree();
    pos += 2;
    rightSon[v] = buildTree();
    pos++;

    return v;
}

void dfs( int v ) {
    if ( type[v] == 0 ) {
        minn[v] = maxx[v] = sz[v] = 1;
        return;
    }

    int l = leftSon[v], r = rightSon[v];
    dfs( l );
    dfs( r );

    if ( type[v] == 1 ) {
        minn[v] = min( minn[l], minn[r] );
        maxx[v] = maxx[l] + maxx[r] - 1;
    } else {
        minn[v] = minn[l] + minn[r];
        maxx[v] = max( sz[l] + maxx[r], sz[r] + maxx[l] );
    }
    sz[v] = sz[l] + sz[r];
};

int main() {
    cin >> s;

    pos = 0;
    buildTree();

    dfs( 1 );

    cout << maxx[1] - minn[1] + 1 << "\n";

    return 0;
}

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