Submission #662108

#	Time	Username	Problem	Language	Result	Execution time	Memory
662108		fatemetmhr	Homework (CEOI22_homework)	C++17	100 / 100	193 ms	149704 KiB

Main

// heiy ... ye rooze jadid ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e6 + 10;

int l[maxn5], r[maxn5], sz[maxn5];
vector <int> adj[maxn5], av;
bool ty[maxn5];

void dfs(int v){
    if(adj[v].empty()){
        l[v] = r[v] = 1;
        sz[v] = 1;
        return;
    }
    int u = adj[v][0], w = adj[v][1];
    dfs(u); dfs(w);
    sz[v] = sz[u] + sz[w];
    if(ty[v]){
        int tmpl = sz[u] - r[u] + 1, tmpr = sz[u] - (l[u] - 1);
        l[u] = tmpl; r[u] = tmpr;
        swap(u, w);
        tmpl = sz[u] - r[u] + 1; tmpr = sz[u] - (l[u] - 1);
        l[u] = tmpl; r[u] = tmpr;
    }
    r[v] = sz[v] - (sz[u] - r[u] + sz[w] - r[w] + 1);
    l[v] = min(l[u], l[w]);
    if(ty[v]){
        int tmpl = sz[v] - r[v] + 1, tmpr = sz[v] - (l[v] - 1);
        l[v] = tmpl; r[v] = tmpr;
    }
    /*
    cout << "ok " << v << ' ' << u << ' ' << w << ' ' << ty[v] << ' ' << l[v] << ' ' << r[v] << ' ' << sz[v] << endl;
    cout << l[u] << ' ' << r[u] << ' ' << sz[u] << endl;
    cout << l[w] << ' ' << r[w] << ' ' << sz[w] << endl;
    */
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    string s; cin >> s;
    int n = s.size(), newnode = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'm'){
            if(av.size())
                adj[av.back()].pb(newnode);
            av.pb(newnode);
            ty[newnode] = (s[i + 1] == 'a' ? 1 : 0);
            i += 3; newnode++;
        }
        else if(s[i] == ')'){
            av.pop_back();
        }
        else if(s[i] == '?'){
            adj[av.back()].pb(newnode);
            newnode++;
        }
    }
    dfs(0);
    cout << r[0] - l[0] + 1 << endl;
}

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