Submission #1054996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054996		gagik_2007	Homework (CEOI22_homework)	C++17	100 / 100	142 ms	171860 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=2000007;
ll n,m,k;
int tp[N];
int l[N],r[N];
int x[N],y[N];
int sz[N];
int cur=1;
int ind=0;
vector<int>g[N];
string s;

int parse(){
    int v=cur;
    cur++;
    char c=s[ind];
    ind++;
    if(c=='?'){
        tp[v]=0;
        return v;
    }
    c=s[ind];
    ind+=3;
    if(c=='i'){
        tp[v]=1;
    }
    else{
        tp[v]=2;
    }
    int lft=parse();
    ind++;
    int rgh=parse();
    l[v]=lft;
    r[v]=rgh;
    ind++;
    return v;
}

void recurs(int v){
    if(tp[v]==0){
        x[v]=y[v]=1;
        sz[v]=1;
        return;
    }
    recurs(l[v]);
    recurs(r[v]);
    sz[v]=sz[l[v]]+sz[r[v]];
    if(tp[v]==1){
        x[v]=min(x[l[v]],x[r[v]]);
        y[v]=y[l[v]]+y[r[v]]-1;
    }
    else{
        x[v]=x[l[v]]+x[r[v]];
        y[v]=max(y[l[v]]+sz[r[v]],y[r[v]]+sz[l[v]]);
    }
    // cout<<v<<": "<<x[v]<<" "<<y[v]<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Binput.txt","r",stdin);
    // freopen("Boutput.txt","w",stdout);
    cin>>s;
    int root=parse();
    recurs(root);
    cout<<y[root]-x[root]+1<<endl;
}

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