Submission #901604

#	Time	Username	Problem	Language	Result	Execution time	Memory
901604		Shayan86	Homework (CEOI22_homework)	C++17	100 / 100	369 ms	292816 KiB

Main

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e6 + 50;
const ll Mod = 1e9 + 7;

int n, m, k, vas[N], L[N], R[N];

string s;
vector<int> adj[N];

void dfs(int v, int p = 0){
    vector<int> ch;
    for(int u: adj[v]){
        if(u != p){
            dfs(u, v); ch.pb(u);
        }
    }
    if(ch.empty()){
        L[v] = 0; R[v] = 0;
        return;
    }

    if(vas[v]){
        R[v] = min(R[ch[0]], R[ch[1]]);
        L[v] = L[ch[0]] + L[ch[1]] + 1;
    }
    else{
        L[v] = min(L[ch[0]], L[ch[1]]);
        R[v] = R[ch[0]] + R[ch[1]] + 1;
    }
}

int main(){
    fast_io;

    cin >> s;
    m = s.size();

    vector<int> path;
    for(int i = 0; i < m;){
        if(s[i] == 'm'){
            int v = ++n;
            if(s[i+1] == 'a') vas[v] = 1;
            if(!path.empty()){
                int u = path.back();
                adj[u].pb(v);
                adj[v].pb(u);
            }
            path.pb(v);
            i += 4;
        }
        else if(s[i] == ',') i++;
        else if(s[i] == '?'){
            int v = ++n;
            if(!path.empty()){
                int u = path.back();
                adj[u].pb(v);
                adj[v].pb(u);
            }
            i++; k++;
        }
        else{
            path.pop_back(); i++;
        }
    }

    dfs(1);

    cout << max(0, k - L[1] - R[1]);

}

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